Skip to content

Research at St Andrews

Forbidden subgraphs of power graphs

Research output: Contribution to journalArticlepeer-review

DOI

Open Access permissions

Open

Author(s)

Pallabi Manna, Peter J. Cameron, Ranjit Mehatari

School/Research organisations

Abstract

The undirected power graph (or simply power graph) of a group G, denoted by P(G), is a graph whose vertices are the elements of the group G, in which two vertices u and v are connected by an edge between if and only if either u = vi or v = uj for some i,j.

A number of important graph classes, including perfect graphs, cographs, chordal graphs, split graphs, and threshold graphs, can be defined either structurally or in terms of forbidden induced subgraphs. We examine each of these five classes and attempt to determine for which groups G the power graph P(G) lies in the class under consideration. We give complete results in the case of nilpotent groups, and partial results in greater generality. In particular, the power graph is always perfect; and we determine completely the groups whose power graph is a threshold or split graph (the answer is the same for both classes). We give a number of open problems.
Close

Details

Original languageEnglish
Article numberP3.4
Number of pages14
JournalElectronic Journal of Combinatorics
Volume28
Issue number3
DOIs
Publication statusPublished - 2 Jul 2021

Discover related content
Find related publications, people, projects and more using interactive charts.

View graph of relations

Related by author

  1. The geometry of diagonal groups

    Bailey, R. A., Cameron, P. J., Praeger, C. E. & Schneider, C., 7 Jul 2021, (E-pub ahead of print) In: Transactions of the American Mathematical Society. Early View

    Research output: Contribution to journalArticlepeer-review

  2. Diagonal groups and arcs over groups

    Bailey, R. A., Cameron, P. J., Kinyon, M. & Praeger, C., 4 Jul 2021, (E-pub ahead of print) In: Designs, Codes and Cryptography. 11 p.

    Research output: Contribution to journalArticlepeer-review

  3. Graphs defined on groups

    Cameron, P. J., 15 Apr 2021, (E-pub ahead of print) In: International Journal of Group Theory. In Press

    Research output: Contribution to journalArticlepeer-review

  4. Groups generated by derangements

    Bailey, R. A., Cameron, P. J., Giudici, M. & Royle, G. F., 15 Apr 2021, In: Journal of Algebra. 572, p. 245-262

    Research output: Contribution to journalArticlepeer-review

  5. Undirecting membership in models of Anti-Foundation

    Adam-Day, B. & Cameron, P. J., Apr 2021, In: Aequationes Mathematicae. 95, 2, p. 393-400 8 p.

    Research output: Contribution to journalArticlepeer-review

Related by journal

  1. The non-commuting, non-generating graph of a nilpotent group

    Cameron, P. J., Freedman, S. D. & Roney-Dougal, C. M., 29 Jan 2021, In: Electronic Journal of Combinatorics. 28, 1, 15 p., P1.16.

    Research output: Contribution to journalArticlepeer-review

  2. The cycle polynomial of a permutation group

    Cameron, P. J. & Semeraro, J., 25 Jan 2018, In: Electronic Journal of Combinatorics. 25, 1, 13 p., P1.14.

    Research output: Contribution to journalArticlepeer-review

  3. On the structure of the power graph and the enhanced power graph of a group

    Aalipour, G., Akbari, S., Cameron, P. J., Nikandish, R. & Shaveisi, F., 27 Jul 2017, In: Electronic Journal of Combinatorics. 24, 3, 18 p., 3.16.

    Research output: Contribution to journalArticlepeer-review

  4. Algebraic properties of chromatic roots

    Cameron, P. J. & Morgan, K., 3 Feb 2017, In: Electronic Journal of Combinatorics. 24, 1, 14 p., P1.21.

    Research output: Contribution to journalArticlepeer-review

ID: 274497442

Top