Forbidden Induced Subgraphs of Power Graphs of Finite Groups

Abstract

For different algebraic structures like groups, semigroups, rings, vector spaces, etc, we can prescribe various graph structures. The power graph is one such major graph representation which was initially defined for semigroups using the power associative law. The directed power graph of semigroup S is a digraph with vertex set is S and for u; v 2 S, u 6= v, there is an arc (u; v) if v = us for some natural number s. The corresponding underlying graph is referred as the (undirected) power graph of S. Above definition remains similar for power graph of groups. For a finite group G, its power graph is denoted by P(G).
Forbidden subgraph plays significant role in graph theory. A number of important graph classes including threshold graphs, split graphs, chordal graphs, cographs and perfect graphs can be defined in terms of forbidden induced subgraphs. A graph is called H–free if it does not contain H as its induced subgraphs. In this case H is said to be the forbidden subgraph of 􀀀. Our problem is to characterize groups of finite order G for which P(G) belongs to either of the classes of forbidden subgraps. In this regard, our major conclusion is that every power graph is perfect.
A graph is called cograph if it forbids P4. We completely characterize the nilpotent groups having P4-free power graph. We identify finite groups G and H for which the power graph of G _ H is P4-free. For finite simple groups we show that in most of the cases their power graphs are not cographs: the only ones for which the power graphs are cographs are the cyclic groups Cp, PSL(3; 4), certain PSL(2; q), certain Sz(q) and the alternating groups A5 and A6. However, a complete determination of these groups involve some hard number-theoretic problems.
A simple graph is said to be a chordal graph if it does not possess any chordless cycle of vertices four or more. In this thesis we investigate chordalness of power graph of finite groups. First we characterize direct product of finite groups having chordal power graph. We classify all simple groups of Lie type whose power graph is chordal. Further we conclude: no sporadic simple group has a chordal power graph. We also show that almost all groups of order upto 47 has chordal power graph.
A graph 􀀀 is self-complementary if 􀀀 = 􀀀. In this thesis we investigate the existence of G such that P(G) is self-complementary. Now if a graph is not self-complementary the natural question arise: how close it is to be a self-complementary graph? A way to measure this is the self-complementary index of the graph. The self-complementary index of 􀀀 is the largest order of a graph 􀀀0 such that both 􀀀0 and 􀀀0 are induced subgraphs of 􀀀. We provide a upper and lower bounds of this index. Moreover we recognize which proper power graphs are complementary in the sense of different classes of forbidden subgraphs as well in sense of different graph theoretic properties like unicyclicity, 2-connectedness, etc.