Forbidden subgraphs of power graphs

DOI10.37236/9961zbMATH Open1467.05115arXiv2010.05198OpenAlexW3182166453MaRDI QIDQ2040001FDOQ2040001

Pallabi Manna, Peter J. Cameron, Ranjit Mehatari

Publication date: 6 July 2021

Published in: The Electronic Journal of Combinatorics (Search for Journal in Brave)

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=v^i$ or $v=u^j$ 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.

Full work available at URL: https://arxiv.org/abs/2010.05198

File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

Mathematics Subject Classification ID

Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Perfect graphs (05C17)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Geometric algorithms and combinatorial optimization
• Normal hypergraphs and the perfect graph conjecture
• Graph Classes: A Survey
• Prime graph components of finite groups
• Threshold graphs and related topics
• Incidence matrices and interval graphs
• Perfect graphs
• The strong perfect graph theorem
• Recognition of alternating groups of prime degree from their element orders
• Undirected power graphs of semigroups
• The power graph of a finite group
• The characterization of finite groups with abelian Sylow 2-subgroups
• A decomposition theorem for partially ordered sets
• A Graph-Theoretic Characterization of the $\text{PV}_{\text{chunk}}$ Class of Synchronizing Primitives
• Power graphs: A survey
• Split Graphs Having Dilworth Number Two
• Directed graphs and combinatorial properties of semigroups
• The power graph of a finite group, II
• On the Connectivity of Proper Power Graphs of Finite Groups
• Dacey Graphs
• On finite groups with dihedral Sylow 2-subgroups
• On the chromatic number of the power graph of a finite group
• The diameter of power graphs of symmetric groups
• On the structure of the power graph and the enhanced power graph of a group
• Vertex connectivity of the power graph of a finite cyclic group
• On the connectivity and independence number of power graphs of groups
• The power graph of a torsion-free group

Cited In (19)

• Certain properties of the power graph associated with a finite group.
• Forbidden subgraph decomposition
• Degree powers in graphs with forbidden subgraphs
• The power graph of a torsion-free group determines the directed power graph
• Title not available (Why is that?)
• On finite groups whose power graph is a cograph
• Forbidden subgraphs in reduced power graphs of finite groups
• Some new results concerning power graphs and enhanced power graphs of groups
• On the difference of the enhanced power graph and the power graph of a finite group
• Descending endomorphism graphs of groups
• Recent developments on the power graph of finite groups – a survey
• Finite groups whose power graphs are cographs
• Line graph characterization of power graphs of finite nilpotent groups
• Classification of non-solvable groups whose power graph is a cograph
• Forbidden subgraphs of co-prime graphs of finite groups
• On groups with chordal power graph, including a classification in the case of finite simple groups
• Graphs defined on groups
• Power graphs of all nilpotent groups
• Forbidden subgraphs in enhanced power graphs of finite groups

This page was built for publication: Forbidden subgraphs of power graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2040001)