Power Graph Classes and Overfullness

Elie Feinsilber · 2025

Read Power Graph Classes and Overfullness by Elie Feinsilber (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2508-01417.txt.

Introduction

Take a finite group and draw a graph where each element links to its powers. Elie Feinsilber asks how few colors the edges of such power graphs need. A graph is overfull when its edges crowd so densely that perfect coloring is impossible. Feinsilber proves a crisp characterization: the power graph is overfull exactly when its coloring number jumps a class, and that happens exactly for cyclic groups of odd prime power order.

Sibling graphs get the same treatment. The intersection power graph and the enhanced power graph each receive their own sharp conditions. The proper power graph is investigated as well. A final result asks when partial colorings can always be extended to the bigger graph without recoloring. The paper ties group structure to coloring fate with unusual completeness.

Catalog record

CREATORElie Feinsilber
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE18 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2508-01417

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Power Graph Classes and Overfullness Elie Feinsilber Abstract In this paper, we investigate the edge-coloring number of the power graph of a finite group. We characterize which finite groups have overfull power graphs, showing that this occurs if and only if the group is cyclic of odd prime power order. We then show that this classifies the class of power graphs: The power graph of a finite group is Class 2 if and only if the group is cyclic of odd prime power order. 1 Introduction The study of graph defined on groups has been a growing area of research in the last decades. The study of these is not new as Cayley graphs have been around for some time, but their study was brought a new perspective when Kelarev and Quinn [ 10 ] introduced the directed power graph in 2002, a directed graph with vertex set the elements of a group and where x\rightarrow y if y is a power of x . Motivated by this, Chakrabarty, Ghosh, and Sen [ 3 ] introduced the power graph : the simple graph \mathscr{G}(G) with vertex set the elements of G and where a\sim b if and only if one is a power of the other. This power graph, as well as other graph defined on algebraic structures, like the enhanced power graph, or the commuting graph, have been studied in more length than before in recent years. A good overview of the results and current progress can be found in [ 11 ] . One of the more natural graph-theoretic questions that can often be asked of graphs, and has many applications, is to ask what its edge-coloring numbers is. We use \chi^{\prime}(\Gamma) to denote the minimal number of colors required to edge-color a graph \Gamma (i.e. such that no two adjacent edges have the same color). It was shown by Vizing ( [ 16 ] ) and Gupta ( [ 8 ] ) independently that, for any graph, its coloring number is either the maximum degree of any vertex in the graph, or one more. We denote by \Delta(\Gamma) the largest degree of any vertex in the graph. Theorem 1.0.1 . (Vizing, Gupta) For every graph \Gamma , \Delta(\Gamma)\leq\chi^{\prime}(\Gamma)\leq\Delta(\Gamma)+1 . Following this theorem, graphs with \chi^{\prime}(\Gamma)=\Delta(\Gamma) are referred to as Class 1 and graphs with \chi^{\prime}(\Gamma)=\Delta(\Gamma)+1 are referred to as Class 2. We remark that determining whether a graph is Class 1 is an NP-complete problem (Holyer in [ 9 ] ). A few tools seem to have been very useful in study of edge-colorings of graphs. Given a graph \Gamma on n vertices, we say that \Gamma is overfull if |E(\Gamma)|/\lfloor\frac{n}{2}\rfloor>\Delta(\Gamma) , where \Delta(\Gamma) denotes the maximum vertex degree in \Gamma . If \Gamma is overfull, then \chi^{\prime}(\Gamma)=\Delta(\Gamma)+1 as no color can be used for more than \lfloor\frac{n}{2}\rfloor edges. One other tool for looking at edge colorings is what is called the core of a graph. The core of \Gamma , denoted by \Gamma_{\Delta} , is the subgraph of \Gamma induced by the vertices of degree \Delta(\Gamma) . This core has implications on the class of a graph: Theorem 1.0.2 . (Vizing [ 15 ] ) If \Gamma_{\Delta} has at most two vertices, then G is class 1. Theorem 1.0.3 . (Fournier [ 7 ] ) If \Gamma_{\Delta} contains no cycle, then G is class 1. Finally, Chetwynd and Hilton made a conjecture about edge colorings: Overfull Conjecture. (Chetwynd and Hilton [ 4 ] ) A graph \Gamma with \Delta(\Gamma)>\frac{n}{3} is class 2 if and only if it has an overfull subgraph S such that \Delta(\Gamma)=\Delta(S) . Some progress was made on the conjecture in various papers by Chetwynd and Hilton ( [ 6 ] , [ 5 ] ), Plantholt ( [ 12 ] , [ 13 ] ), and subsequently Rhee ( [ 14 ] ) the combination of which amounted to the following theorem: Theorem 1.0.4 . Let G be a simple graph with \Delta(\Gamma)\geq|V(\Gamma)|-3 . Then \Gamma is Class 2 if and only if \Gamma contains an overfull subgraph H with \Delta(H)=\Delta(\Gamma) . Back to power graphs, since the identity element of the group G is a power of every element of the group, we can get a clearer idea of the structure the graph. Notably, the following result of Cameron is very useful to us. Proposition 1.0.5 . [ 2 ] Let G be a finite group; let S be the set of vertices of the power graph \mathcal{G}(G) which are joined to all other vertices. Suppose that |S|>1 . Then one of the following occurs: 1. G is cyclic of prime power order, and S=G ; 2. G is cyclic of non-prime-power order n , and S consists of the identity and the generators of G , so that |S|=1+\varphi(n) ; 3. G is generalised quaternion, and S contains the identity and the unique involution in G , so that |S|=2 . 2 Results We will now consider the graph-theoretic concepts outlined above specifically for power graphs of finite groups. Proposition 2.0.1 . If |G| is even, then \mathscr{G}(G) is not overfull. Proof. Say |G|=2n . Then \displaystyle\frac{|E(\mathscr{G}(G))|}{\lfloor 2n/2\rfloor}>2n-1 \displaystyle\Leftrightarrow|E(\mathscr{G}(G))|>\frac{2n(2n-1)}{2} which never holds since a complete graph on 2n vertices has \frac{2n(2n-1)}{2} edges. ∎ Lemma 2.0.2 . If G is a group of odd order with |G|=2n+1 , then, to be overfull, \mathscr{G}(G) can lose at most n-1 edges compared to K_{2n+1} . Proof. For \mathscr{G}(G) to be overfull, we need \mathscr{G}(G) to have \displaystyle\frac{|E(\mathscr{G}(G))|}{\lfloor(2n+1)/2\rfloor}>2n\Leftrightarrow\frac{|E(\mathscr{G}(G))|}{\lfloor 2n/2\rfloor}>2n\Leftrightarrow|E(\mathscr{G}(G))|>2n^{2}\text{ edges. } Now, \displaystyle\frac{2n(2n+1)}{2}-(2n^{2}+1)=\frac{2n(2n+1-2n)}{2}-1=n-1 So we may lose up to n-1 edges if we want to remain overfull. ∎ Proposition 2.0.3 . If only the identity is joined to all other vertices, then \mathscr{G}(G) is not overfull. Proof. From before, if |G| is even, then \mathscr{G}(G) is not overfull. So say |G|=2n+1 and only the identity is joined to all other vertices. Then every other element, 2n of them, must have at least one vertex to which it is not adjacent. That’s at least n missing edges, hence breaking the requirement of the above lemma. Therefore if only the identity is joined to all other vertices, \mathscr{G}(G) is not overfull. ∎ Proposition 2.0.4 . If G is a cyclic group of odd prime-power order, then \mathscr{G}(G) is overfull. Proof. If G is a cyclic group of odd prime power order, then \mathscr{G}(G) is complete as shown in Prop 1.0.5 . In which case we have \frac{2n(2n+1)}{2}=2n^{2}+n edges which is more than the necessary 2n^{2} . ∎ Lemma 2.0.5 . If G is a cyclic group of odd order which is not a prime power, then G is not overfull. Proof. Let |C_{2n+1}|=p_{1}^{a_{1}}\cdot p_{2}^{a_{2}}\cdot p_{3}^{a_{3}}\cdot...\cdot p_{r}^{a_{r}} . For each p_{i}^{a_{i}} , the Euler totient function \varphi(\frac{2n+1}{p_{i}^{a_{i}}}) gives the number of elements of order p_{i}^{a_{i}} in C_{2n+1} and in the cyclic subgroup generated by p_{i}^{a_{i}} . So we have disjoint cliques (since the identity doesn’t share their order it is not included in the count) on \varphi(\frac{2n+1}{p_{i}^{a_{i}}}) elements for each p_{i}^{a^{i}} . Now \frac{2n+1}{p_{i}^{a_{i}}} is always gives a product of primes, so we have cliques on \varphi(\frac{2n+1}{p_{i}^{a_{i}}})=\varphi(p)\varphi(q)...=(p-1)(q-1)... vertices. Now for any two cliques on (p-1) and (q-1) elements, we are missing (p-1)(q-1)=pq-(p+q)+1 edges. And since p+q is

Read the complete text