On forbidden subgraphs of main supergraphs of groups

1.   Introduction

In the realm of algebraic structures, which encompass entities such as groups and rings, a prevalent avenue of investigation involves the establishment of graphs that correspond to these structures and the subsequent analysis of their graph representations. This topic constitutes a prominent area of inquiry within algebraic graph theory, attracting significant scholarly attention. A noteworthy example in this domain is the widely recognized Cayley graph, which is a construct rooted in group theory with a distinguished historical lineage. Furthermore, the examination of graphs linked to algebraic structures has yielded practical applications of considerable importance, as evidenced in prior works such as [1]. For instance, Cayley graphs have been effectively leveraged as classifiers in the domain of data mining, as articulated in [2].

The power graph constitutes another prominent graph representation within the domain of group theory. Specifically, the undirected power graph of a group $G$, denoted as $\mathcal{P}(G)$, is a graph with a vertex set $G$, and two distinct vertices are adjacent if one is a power of the other. Originating from the seminal work of Kelarev and Quinn [3], the idea of the power graph of a group has been introduced, which is a directed graph. Subsequently, Chakrabarty et al.[4] raised the notion of the undirected power graph of a group, as documented in [5]. Over the past two decades, research attention directed towards power graphs of groups has witnessed a notable surge. A comprehensive exposition of pertinent findings and unresolved inquiries regarding power graphs is available in the survey papers [6,7]. Furthermore, another salient graph representation associated with groups is the (non-)commuting graph. Investigative efforts on the commuting and non-commuting graphs of finite groups were documented in [8] and [9], respectively. The spectrum of a graph has emerged as a pivotal avenue to discern fundamental characteristics such as diameter and connectivity. Notably, spectral investigations into commuting and non-commuting graphs of finite groups were undertaken in [10] and [11], respectively.

The main supergraph of a finite group $G$, denoted as $\mathcal{S}(G)$, is an undirected, simple graph with the vertex set $G$ in which two distinct vertices $a$ and $b$ are adjacent in $\mathcal{S}(G)$ if the order of one is a divisor of the order of the other. The origin idea of the main supergraph can be linked to the research conducted by Hamzeh and Ashrafi [12], who initially denoted $\mathcal{S}(G)$ as the supergraph of the power graph of $G$. Subsequently, in 2018, Hamzeh and Ashrafi [13] coined the term "order supergraph" for the main supergraph $\mathcal{S}(G)$ and conducted an in-depth exploration of its properties, along with establishing connections between $\mathcal{S}(G)$ and the power graph $\mathcal{P}(G)$. Notably, in their seminal work [13], the authors posed an intriguing inquiry: what structural properties characterize group $G$ such that the number of prime divisors of $|G|$ equals the independence number of $\mathcal{S}(G)$? This question was subsequently addressed by Ma and Su in [14], where they examined the independence number of the main supergraph and offered a solution to the aforementioned query. Furthermore, investigations into the Hamiltonicity and Eulerianness of $\mathcal{S}(G)$ were undertaken in [15], while spectral analyses, including spectrum and $L$-spectrum, were conducted by Hamzeh and Ashrafi in [16]. In a separate study, Asboei and Salehi [17] delved into Thompson's problem by determining the projective linear groups based on their main supergraphs. In a recent contribution [18], Asboei and Salehi made significant strides by identifying numerous families of finite non-solvable groups based upon their main supergraphs, marking substantial progress in resolving Thompson's problem.

In the context of graph theory, let $\Gamma$ be a graph; a graph is $\Gamma$-free if it contains no induced subgraphs isomorphic to $\Gamma$. A multitude of graph classes of significant importance are defined either by their inherent structural properties or by forbidden subgraphs. Illustratively, under the structural definition, a split graph is characterized by the partition of its vertex set into the disjoint union of an independent set and a clique, with the possibility of either set being empty. This contains both complete graphs and null graphs within the realm of split graphs. A split graph is a graph containing no induced subgraphs isomorphic to any of the three following designated forbidden graphs: $C_4$, $C_5$, and $2K_2$ (cf. [19]). A graph is called a cograph if it contains no induced subgraphs isomorphic to $P_4$. Cographs are the smallest class of graphs that include the $1$-vertex graph, and demonstrate closure properties with respect to the operations of disjoint union and complementation. Moreover, a threshold graph is a graph that does not contain any induced subgraph isomorphic to any of the three following designated forbidden graphs: $P_4$, $C_4$, and $2K_2$. It follows that every threshold graph is a cograph. Threshold graphs constitute the smallest family of graphs that contain the $1$-vertex graph and demonstrate closure properties with respect to the operations of adding an isolated vertex and adding a vertex joined to all others. Notably, threshold graphs find applications in the domain of computer science (cf. [20]).

Recently, Cameron [21] undertook a comprehensive survey of various graph structures defined upon groups, including power graphs, commuting graphs, enhanced power graphs, intersection graphs, Gruenberg-Kegel graphs, non-generating graphs, and others. These diverse graph constructs were systematically examined within the framework of B superA graphs in [22], which facilitated a unified approach to their investigation. Notably, Cameron posed a pivotal inquiry in [21], and sought to elucidate for which finite groups a certain graph is either a perfect graph, a cograph, a split graph, or a theshold graph (see [21, Question 14]). It is obvious that the power graph $\mathcal{P}(G)$ forms a spanning subgraph of the main supergraph $\mathcal{S}(G)$. Subsequently, in 2021, Manna et al. [23] conducted an in-depth examination of the forbidden subgraphs of power graphs of finite groups. Motivated by the question posed by Cameron, we are propelled to explore the subsequent inquiry:

Question 1.1. Which finite groups have a main supergraph that is either a perfect graph, a cograph, a split graph, or a threshold graph?

Hamzeh and Ashrafi [13] proved that the main supergraph of a finite group is perfect. In this study, we undertake the task of classifying the finite groups $G$ for which the graph $\mathcal{S}(G)$ exhibits properties of both a split graph and a threshold graph. Additionally, we obtain a characterization of groups wherein $\mathcal{S}(G)$ is a cograph. Additionally, we extend our analysis to classify groups for which $\mathcal{S}(G)$ is a cograph under specific conditions, such as when $G$ is either a direct product of two non-trivial groups, a dihedral group, a generalized quaternion group, a symmetric group, an alternating group, or a sporadic simple group. These findings substantially contribute towards addressing Question 1.1.

2.   Preliminaries

This section presents the foundational definitions concerning groups and graphs. All groups considered in this paper are finite. For consistency, we consistently utilize $G$ to denote a finite group, with $e$ designating its identity element. Meanwhile, the abbreviation "iff" is the same meaning of "if and only if".

Given an element $g$ that belongs to the group $G$, the order of $g$, represented by $o(g)$, is the cardinality of the subgroup, $\langle g\rangle$, generated by $g$. In particular, if the order of $g$ equals $2$, then the element $g$ is called an involution. The center of $G$ is denoted by $Z(G)$, which comprises elements $x$ that satisfy the commutativity property $xy = yx$ for all $y$ in $G$. As usual, $\mathbb{Z}_n$ represents the cyclic group of order $n$. Additionally, given a prime $p$, the elementary abelian $p$-group of order $p^n$ is constructed as the direct product of $n$ cyclic groups $\mathbb{Z}_p$, which is denoted by $\mathbb{Z}_p^n$. The exponent of $G$ is represented by $exp(G)$, which is the smallest positive integer $t$ such that $g^t = e$ is true for every $g$ in $G$. If every Sylow $p$-subgroup of $G$ is a normal subgroup, then $G$ is a nilpotent group. Equivalently, a finite group is nilpotent iff it can be expressed as the direct product of its Sylow subgroups.

All graphs examined in our work are undirected and do not include loops or multiple edges. For a graph $\Gamma$, we denote its vertex set and edge set as $V(\Gamma)$ and $E(\Gamma)$, respectively. We use $C_n$ to denote a cycle with $n$ vertices, whereas $P_n$ is used to denote a path with $n$ vertices. Furthermore, we use $2K_2$ to denote a matching that consists of four vertices, including two separate edges. If $\{x, y\}$ belongs to the set $E(\Gamma)$, then we represent this by using the notation $x\sim_{\Gamma}y$, or alternatively as $x\sim y$. We use the notation $x_1\sim x_2\sim\cdots \sim x_n$ to represent an induced subgraph that is isomorphic to a path $P_n$, where $x_1, x_2, \ldots, x_n\in V(\Gamma)$ are distinct. Such a subgraph contains a vertex set $\{x_1, x_2, \ldots, x_n\}$ and an edge set $\{\{x_i, x_{i+1}\}: 1\le i\le n-1\}$.

The following observation directly follows from the notion of the main supergraph of a group.

Observation 2.1. Suppose $G$ is a group and $H$ is a subgroup of $G$. Then, $\mathcal{S}(H)$ is an induced subgraph of $\mathcal{S}(G)$ by $H$.

By Observation 2.1, the second observation is established.

Observation 2.2. Suppose $G$ is a group. $\mathcal{S}(G)$ is a split graph (a threshold graph and a cograph, respectively) iff $\mathcal{S}(H)$ is a split graph (a threshold graph and a cograph, respectively), for every subgroup $H$ of $G$.

The two aforementioned observations are crucial and will be recurrently employed in the subsequent sections, occasionally without an explicit reference.

3.   Split and threshold graphs

This section categorizes the finite groups whose main supergraph is either a split graph or is a theshold graph. Furthermore, we extend this classification to include finite groups that possess $2K_2$-free main supergraphs.

The following theorem is the main result of this section.

Theorem 3.1. For a finite group $G$, the following statements are equivalent:

$\rm (a)$ $\mathcal{S}(G)$ is split;

$\rm (b)$ $\mathcal{S}(G)$ is threshold;

$\rm (c)$ $\mathcal{S}(G)$ is $2K_2$-free; and

$\rm (d)$ $G$ is isomorphic to either a $p$-group or $\mathbb{Z}_2\times P$, where $P$ is a $p$-group with $exp(P) = p$ for some odd prime $p$.

We use $\pi_e(G)$ to represent the set of orders of all non-trivial elements in $G$ and $\pi(G)$ to present the set consisting of all prime divisors of $|G|$. First, we obtain a few lemmas before the proof of the main result, namely Theorem 3.1.

Lemma 3.2. ([13, Theorem 2.3]) $\mathcal{S}(G)$ is complete iff $G$ is a $p$-group with a prime $p$.

Lemma 3.3. Suppose $P$ is a $p$-group with an odd prime $p$ and $exp(P) = p$. If $G\cong \mathbb{Z}_2\times P$, then $\mathcal{S}(G)$ is $2K_2$-free, $P_4$-free and $C_4$-free. Particularly, $\mathcal{S}(G)$ is both split and threshold.

Proof. Obviously, $\pi_e(G) = \{2, p, 2p\}$, and $G$ has a unique involution, which is denoted as $u$. Consequently, the induced subgraph of $\mathcal{S}(G)$ by the set $G\setminus\{u\}$ is complete, meaning that $\mathcal{S}(G)$ is split. Hence, $\mathcal{S}(G)$ is $2K_2$-free and $C_4$-free according to reference [19]. Furthermore, note that S(G) is likewise $P_4$-free, as expected.

Lemma 3.4. $\mathcal{S}(G)$ is $2K_2$-free iff $G$ is isomorphic to either a $p$-group or $\mathbb{Z}_2\times P$, where $P$ is a $p$-group with an odd prime $p$ and $exp(P) = p$.

Proof. If $G$ is a $p$-group, then $\mathcal{S}(G)$ is complete, and thus is $2K_2$-free. If $G$ is $\mathbb{Z}_2\times P$, where $P$ is a $p$-group of exponent $p$, and $p$ an odd prime, then $G$ is $2K_2$-free by Lemma 3.3, as required. Thus, the sufficiency follows.

Now, we shall establish the necessity. Assume $\mathcal{S}(G)$ is $2K_2$-free. First, we assert that $|\pi(G)|\le 2$. Indeed, if $|\pi(G)|\ge 3$, then $|G|$ has at least two different odd primes, denoted as $q$ and $r$, each greater than or equal to $3$. Consequently, the set $\{a, a^{-1}, b, b^{-1}\}$ induces a subgraph isomorphic to $2K_2$ in $\mathcal{S}(G)$, where elements $a, b\in G$ with $o(a) = q$ and $o(b) = r$. Hence, our assertion holds true. Furthermore, we can infer that $\pi(G)$ does not contain two distinct odd primes. This implies either $|\pi(G)| = 1$ or $|\pi(G)| = 2$ with $2\in \pi(G)$. If $|\pi(G)| = 1$, then $G$ is isomorphic to a $p$-group.

In the subsequent discussion, suppose that the set $\pi(G) = \{2, p\}$ contains an odd prime number $p$.

Let $x\in G$ with $o(x) = p$. Now, two different involutions $u_1$, $u_2$ and $x, x^{-1}$ would induce a subgraph isomorphic to $2K_2$. Consequently, $G$ has a unique involution, denoted as $u$. For any $g\in G$, we observe that $gug^{-1}$ is an involution, which implies that $gug^{-1} = u$. Thus we obtain $gu = ug$. Subsequently, $u\in Z(G)$, and then $o(ux) = 2p$. Assume that $w$ is an element of order $q^2$ for some prime $q$; then, $ux$, $(ux)^{-1}$, $w$, $w^{-1}$ induces $2K_2$ as a subgraph. Consequently, we infer that $4$ and $p^2$ do not belong to $\pi_e(G)$, which also implies the following:

Since $G$ has a unique involution and does not contain any element of order $4$, we infer that $G$ has a unique Sylow $2$-subgroup, $\langle u\rangle\cong\mathbb{Z}_2$.

Let $P$ denote a Sylow $p$-subgroup of $G$. There exists a positive integer $n$ such that $|P| = p^n$. Then, by (3.1), we have $|G| = 2p^n$. Furthermore, (3.1) implies $exp(P) = p$. $P$ is normal in $G$ since $P$ is a subgroup of $G$ with an index $2$. Hence, $G = \langle u\rangle\times P\cong\mathbb{Z}_2\times P$, as intended.

Now, we are ready to prove the main theorem of this section.

Proof of Theorem 3.1. Note that, according to Lemma 3.2, $\Gamma(G)$ is complete for a $p$-group $G$. Therefore, from Lemma 3.3, it follows that part (d) implies parts (a), (b), and (c). Additionally, considering the definitions of a split graph and a threshold graph, both types are $2K_2$-free. Consequently, by Lemma 3.4, any of parts (a), (b), and (c) implies part (d), as intended.

4.   Cographs

This section characterizes the finite groups $G$ with a cograph $\mathcal{S}(G)$ under specific conditions, such as when $G$ is either a direct product of two non-trivial groups, a dihedral group, a generalized quaternion group, a symmetric group, an alternating group, or a sporadic simple group. Furthermore, we will find all finite groups $G$ of the order at most $30$ for which $\mathcal{S}(G)$ is not a cograph.

We employ $\Phi$ to represent the set of finite groups $G$ that meet the following:

${\rm (a)}$ For each $g\in G$, $o(g)$ equals either $p^m$ or $pq$, where $p$ and $q$ ($p\ne q$) are primes and an integer $m\ge 0$;

${\rm (b)}$ If $pq\in\pi_e(G)$ for different primes $p$ and $q$, then $p^2$ and $q^2$ are not elements of $\pi_e(G)$; and

${\rm (c)}$ If $pq, rs\in\pi_e(G)$ where $p$, $q$, $r$, and $s$ are primes with $p\ne q$, $r\ne s$ and $\{p, q\}\neq\{r, s\}$, then $\{p, q\}\cap\{r, s\} = \emptyset$.

If $G\in\Phi$, then $G$ is called a $\Phi$-group.

A finite group is termed a CP-group [24] if every non-trivial element inside this finite group has a prime power order. For instance, the alternating group of degree five is a CP-group. Note that for every prime $p$, a $p$-group is also a CP-group. Delgado and Wu provided a characterization for all finite CP-groups (see [24, Theorem 4]). By virtue of the definition of a $\Phi$-group, we provide the ensuing examples.

Example 4.1. (i) Every CP-group is a $\Phi$-group;

(ii) For distinct primes $p$ and $q$, a group $G$ with $\pi_e(G) = \{p, q, pq\}$ is a $\Phi$-group. In particular, $\mathbb{Z}_p^m\times\mathbb{Z}_q^n$ is a $\Phi$-group for all $m$ and $n$ greater than or equal to $1$; and

(iii) $\pi_e(L_2(29)) = \{2, 3, 5, 7, 14, 15, 29\}$. Therefore, $L_2(29)$ is a $\Phi$-group.

The principal outcome of this section is in the subsequent theorem.

Theorem 4.2. $\mathcal{S}(G)$ is a cograph iff $G$ is a $\Phi$-group.

We derive the subsequent result as corollaries of Theorem 4.2.

Corollary 4.3. $\mathcal{S}(G)$ is a cograph if $G$ is isomorphic to one of the following groups:

${\rm (a)}$ a CP-group;

${\rm (b)}$ $\pi_e(G) = \{pq\}\cup\{r:r\mathit{\text{is prime}}\}$, where $p$ and $q$ ($p\ne q$) are primes; and

${\rm (c)}$ a group of order $pq$, where $p$ and $q$ ($p\ne q$) are primes.

First, we shall present several results before giving the proof of Theorem 4.2.

Lemma 4.4. $\mathcal{S}(G)$ is a cograph if $G$ is a $\Phi$-group.

Proof. To prove this, it is sufficient to demonstrate that $\mathcal{S}(G)$ has no induced subgraphs isomorphic to $P_4$. Suppose, for the sake of contradiction, that $\mathcal{S}(G)$ contains an induced path $P_4$ as follows:

We initially claim that one of the elements $b$ and $c$ must have an order $pq$ where $p$ and $q$ ($p\ne q$) are primes. Now, for the sake of contradiction, we can assume that both $b$ and $c$ have prime power orders. Since $b$ is adjacent to $c$ in $\mathcal{S}(G)$, we assume that $o(b) = p^s$ and $o(c) = p^t$, where $p$ is a prime and $s, t\ge 1$. Subsequently, $o(a)$ must be a product of two different primes, as $a$ and $c$ are non-adjacent. From condition (a) of the definition of a $\Phi$-group, it follows that $o(a) = pq$ and $o(b) = p$, where $q\; (\ne p)$ is a prime number. Moreover, since $a$ and $c$ are non-adjacent, we have $o(c)\neq p$. Consequently, $G$ has an element of order $p^2$, which contradicts condition (b) in the definition of a $\Phi$-group.

We conclude that our claim is valid, namely one of the elements $b$ and $c$ must have an order of $pq$, where $p$ and $q$ ($p\ne q$) are primes. Without loss of generality, suppose that $o(b) = pq$. Then, $o(c)\neq pq$. Consequently, $o(c) = p$ or $q$. Clearly, without loss of generality, we can set $o(c) = p$. Therefore, $o(d)\neq p$. This implies that $o(d) = p^m (m\ge 2)$ or $pr$, where $r$ is a prime with $p\neq r$ and $q\neq r$. However, this contradicts conditions (b) and (c) of the definition of a $\Phi$-group.

Lemma 4.5. Suppose that $\mathcal{S}(G)$ is a cograph. Then, $G$ does not contain any element of the order $pqr$ or $p^2q$, where $p$, $q$, and $r$ are distinct primes.

Proof. Suppose, for the sake of contradiction, that $G$ has an element $a$ with the order $pqr$, where $p$, $q$, and $r$ are distinct primes. One can see easily that

forms an induced path in $\mathcal{S}(G)$ with four vertices. Such a configuration contradicts the assumption that $\mathcal{S}(G)$ is a cograph. Likewise, if $G$ contains an element $b$ of order $p^2q$, where $p$ and $q$ ($p\ne q$) are primes, then $b^{p^2}\sim b^{p}\sim b^{pq}\sim b^{q}$ forms an induced subgraph of $\mathcal{S}(G)$ which is isomorphic to $P_4$, which leads to a contradiction.

The proof of Theorem 4.2 is now presented.

Proof of Theorem 4.2. The sufficiency is evident from Lemma 4.4.

We proceed to establish the necessity. Assuming that $\mathcal{S}(G)$ is a cograph, Lemma 4.5 confirms the satisfaction of condition (a) of the $\Phi$-group definition.

Next, we aim to verify condition (b). Let $pq\in \pi_e(G)$ for two primes $p$ and $q$ ($p\ne q$). For a contradiction, assume that $p^2\in\pi_e(G)$. Consider the elements $a, b\in G$ with $o(a) = pq$ and $o(b) = p^2$. It can be readily verified that $a^{p}\sim a\sim a^{q}\sim b$ forms an induced path of order 4. This contradicts the assumption that $\mathcal{S}(G)$ is a cograph. Similarly, $q^2\notin \pi_e(G)$. Therefore, condition (b) of the definition of a $\Phi$-group is satisfied.

Finally, we demonstrate condition (c) of the definition of a $\Phi$-group. Let $pq, rs\in\pi_e(G)$, where $p$, $q$, $r$, and $s$ are primes such that $p\neq q$, $r\neq s$, and $\{p, q\}\neq\{r, s\}$. Suppose, for the sake of contradiction, that $\{p, q\}\cap\{r, s\}\neq\emptyset$. Thus, $|\{p, q\}\cap\{r, s\}| = 1$. Without loss of generality, let $p = r$ and $q\neq s$. Take $x, y \in G$ with $o(x) = pq$ and $o(y) = ps$. It follows that

forms an induced path isomorphic to $P_4$, which contradicts the fact that $\mathcal{S}(G)$ is $P_4$-free. Thus, condition (c) of the definition of a $\Phi$-group follows, and therefore, $G$ is a $\Phi$-group.

4.1.   Direct product

Given two non-trivial groups, $H$ and $K$, we aim to determine under which conditions the direct product $H\times K$ yields a main supergraph that is a cograph. In this subsection, we will undertake the task of characterizing the direct product $H\times K$ such that its main supergraph is a cograph.

Theorem 4.6. Let $H$ and $K$ be two non-trivial groups. Then, $\mathcal{S}(H\times K)$ is a cograph iff $H$ and $K$ satisfy one of the following conditions:

${\rm (i)}$ Both $H$ and $K$ are $p$-groups for some prime $p$;

${\rm (ii)}$ $exp(H) = p$ and $exp(K) = q$, where $p$ and $q$ ($p\ne q$) are primes; and

${\rm (iii)}$ One of groups $H$ and $K$ is not a $p$-group, $\pi_e(H)\subseteq\{p, q, pq\}$, and $\pi_e(K)\subseteq\{p, q, pq\}$, where $p$ and $q$ ($p\ne q$) are primes.

Proof. If conditions (i) hold for $H$ and $K$, then $H\times K$ is a $p$-group, consequently ensuring that $\mathcal{S}(H\; \times\; K)$ is a cograph. On the other hand, if either condition (ⅱ) or (ⅲ) applies to $H$ and $K$, then it is evident that $\pi_e(H\times K) = \{p, q, pq\}$. Hence, $\mathcal{S}(H\times K)$ is a cograph by Example 4.1(ⅱ) and Theorem 4.2. Therefore, the sufficiency holds.

We proceed to establish the necessity. By Theorem 4.2, $\mathcal{S}(H\times K)$ is a cograph implies that $H\times K$ is a $\Phi$-groups. Given that both $H$ and $K$ are non-trivial, condition (c) of the $\Phi$-group definition implies that $\pi(H)$ has at most two elements.

Let $\pi(H)\subseteq\{p, q\}$, where $p$ and $q$ ($p\ne q$) are primes.

Case 1. $|\pi(H)| = 1$.

Let us assume, without loss of generality, that $\pi(H) = {p}$. If $p^2\in\pi_e(H)$, then condition (a) of the $\Phi$-group definition implies that $K$ is a $p$-group, which indicates that part (ⅰ) holds. Alternatively, if $p^2\notin\pi_e(H)$, which $exp(H) = p$ and $K$ is a $p$-group, then part (ⅰ) holds.

However, if $K$ is a $q$-group, then condition (a) of the $\Phi$-group definition implies $exp(K) = q$, which satisfies part (ⅱ).

Therefore, assuming $|\pi(K)|\ge 2$, it follows from condition (c) of the $\Phi$-group definition that $\pi(K) = \{p, q\}$. Consequently, $H\times K$ contains elements of order $pq$. This leads to the fulfillment of condition (b) of the $\Phi$-group definition, which implies $\pi_e(K)\subseteq\{p, q, pq\}$; thus, part (ⅲ) is satisfied.

Case 2. $\pi(H) = \{p, q\}$.

In this case, it is evident that $\pi(K)\subseteq\{p, q\}$. If $|\pi(H)| = 1$, then $pq\in\pi_e(H\times K)$. Analogously to Case 1, we observe $\pi_e(H)\subseteq\{p, q, pq\}$ and $\pi_e(K)\subseteq\{p, q, pq\}$, which implies the fulfillment of part (ⅲ). Finally, assuming $\pi(K) = \{p, q\}$, a similar deduction reveals $\pi_e(H)\subseteq\{p, q, pq\}$ and $\pi_e(K)\subseteq\{p, q, pq\}$, thus ensuring the satisfaction of part (ⅲ).

It is a recognized fact in group theory that a finite group is a nilpotent group iff it can be expressed as the direct product of its Sylow subgroups. In such groups, elements of distinct prime orders are commutative. As a consequence derived from Theorem 4.6, we characterize all finite nilpotent groups for which the main supergraph is a cograph.

Corollary 4.7. For a finite, nilpotent group $G$, the main supergraph $\mathcal{S}(G)$ is a cograph iff $G$ is either a $p$-group or a direct product $P \times Q$, where $exp(P) = p$ and $exp(Q) = q$ with two distinct primes $p$ and $q$.

By the fundamental theorem of finite abelian groups and Corollary 4.7, we can classify all abelian groups for which the main supergraph is a cograph.

Corollary 4.8. An abelian group $G$ satisfies the condition that $\mathcal{S}(G)$ is a cograph iff $G$ is isomorphic to the following:

where $p$ and $q$ ($p\ne q$) are primes, and $m$, $n$, and $\alpha_i$ (for all $1\le i\le t$) are positive integers.

4.2.   Dihedral groups and generalized quaternion groups

For any positive integer $n$, the dihedral group of order $2n$, which is denoted by $D_{2n}$, represents the symmetries of a regular polygon with $n$ vertices, including both rotations and reflections. When $n\ge 3$, $D_{2n}$ is non-abelian and is significant in group theory, geometry, and chemistry. Moreover, the occurrence of $D_{2n}$ is prevalent in art and nature. The presentation of $D_{2n}$ is as follows:

It is straightforward to confirm that we have $o(a^ib) = 2$ for all $1\le i \le n$. Additionally,

forms a partition of $D_{2n}$.

By Corollary 4.8, we have the following lemma, which classifies all cyclic groups whose main supergraph is a cograph.

Lemma 4.9. $\mathcal{S}(\mathbb{Z}_n)$ is a cograph iff $n = p^m$ or $pq$, where $p$ and $q$ ($p\ne q$) are primes, and an integer $m\ge 1$.

Theorem 4.10. Let $D_{2n}$ be the dihedral group as defined in (4.1). Then, $\mathcal{S}(D_{2n})$ is a cograph iff $n = p^m$ or $pq$, where $p$ and $q$ ($p\ne q$) are primes and $m$ is a positive integer.

Proof. If $\mathcal{S}(D_{2n})$ is a cograph, then the main supergraph of any subgroup of the dihedral group $D_{2n}$ is also a cograph. As a result, $\mathcal{S}(\langle a\rangle)$ is necessarily a cograph. According to Lemma 4.9, we may conclude that $n$ is either $p^m$ or $pq$, where $p$ and $q$ ($p\ne q$) are primes and $m$ is a positive integer.

Now, if $n = p^m$ with a prime $p$ and an integer $m\ge 1$, then $D_{2n}$ is a CP-group based on (4.2). Thus $\mathcal{S}(D_{2n})$ is a cograph based on Corollary 4.3(a). If $n$ is the product of two different primes $p$ and $q$, then (4.2) indicates that $\pi_e(D_{2n})$ is the union of $\{pq\}$ and a set consisting of some primes. Therefore, according to Corollary 4.3(b), we conclude that $\mathcal{S}(D_{2n})$ is a cograph, as intended.

Let $n\ge 2$. Johnson [25, pages 44 and 45] presented the definition of a generalized quaternion group $Q_{4n}$ of order $4n$ using the following:

Note this is sometimes called a dicyclic group. In addition, it is evident that $Q_{4n}$ has a unique involution in which $x^n = y^2$. Moreover, for any $1\le i \le 2m$, we have that $o(x^iy) = 4$, and

is a partition of $Q_{4n}$.

Theorem 4.11. Let $Q_{4n}$ be the generalized quaternion group as defined in (4.3). Then, $\mathcal{S}(Q_{4n})$ is a cograph iff $n = 2^m$ with an integer $m\ge 1$.

Proof. Suppose that $\mathcal{S}(Q_{4n})$ is a cograph. It follows that $\mathcal{S}(\langle x\rangle)$, where $x$ has an order $2n$, is also a cograph. By applying Lemma 4.9, we deduce that $n$ is either $2^m$ or $p$ with an odd prime $p$ and an integer $m\ge 1$.

To complete the proof, we aim to show that $n\ne p$. Assume, for the sake of contradiction, that $n = p$ with an odd prime $p$. This implies that $2p\in \pi_e(G)$. However, according to Theorem 4.2, we know that $4$ cannot be an element of $\pi_e(G)$. Nonetheless, the element $y\in Q_{4n}$ has the order $4$, which leads to a contradiction.

Conversely, let $n$ be a power of $2$. Then, as per (4.4), $Q_{4n}$ is a $2$-group. Consequently, $\mathcal{S}(Q_{4n})$ is a cograph, thereby completing the proof.

4.3.   Symmetric groups and alternating groups

The symmetric group of order $n!$, denoted by $\mathbf{S}_n$, is comprised of all permutations of a set with size $n$. This group is important in various mathematical domains, including combinatorics and group theory, as every finite group is a subgroup of some symmetric group. It's worth noting that $\mathbf{S}_n$ is abelian iff $n\leq 2$.

Theorem 4.12. $\mathcal{S}(\mathbf{S}_n)$ is a cograph iff $n\le 4$.

Proof. Note that $\pi_e(\mathbf{S}_4) = \{2, 3, 4\}$. Therefore, $\mathbf{S}_4$ is a CP-group, and consequently, $\mathbf{S}_n$ is a CP-group for all $n\leq 4$. This implies that $\mathcal{S}(\mathbf{S}_n)$ is a cograph by Corollary 4.3(a) for all $n\leq 4$. It's worth noting that $\mathcal{S}(\mathbf{S}_5)$ is an induced subgraph of $\mathcal{S}(\mathbf{S}_n)$ for any $n\geq 6$. To complete the proof, it suffices to show that $\mathcal{S}(\mathbf{S}_5)$ is not a cograph. Indeed, $\{(12)(345), (1234)\}\subseteq\mathbf{S}_5$, where $o((12)(345)) = 6$ and $o((1234)) = 4$, indicating that $\mathbf{S}_5$ is not a $\Phi$-group. This implies that $\mathcal{S}(\mathbf{S}_5)$ is not a cograph by Theorem 4.2, as required.

In the symmetric group $\mathbf{S}_n$, the set of all even permutations forms a subgroup known as the alternating group on $n$ letters, denoted by $\mathbf{A}_n$. It is worth noting that $\mathbf{A}_n$ is a simple group for any $n\geq 5$.

Theorem 4.13. $\mathcal{S}(\mathbf{A}_n)$ is a cograph iff $n\le 6$.

Proof. Note that $\mathbf{A}_6$ is a CP-group. Hence, for any $n\le 6$, we have that $\mathbf{A}_n$ is a CP-group. Consequently, $\mathcal{S}(\mathbf{S}_n)$ is a cograph according to Corollary 4.3(a) for each $n\le 4$. Now, it suffices to prove that $\mathcal{S}(\mathbf{A}_7)$ is not a cograph. Since $\mathbf{A}_7$ contains two elements $(123)(45)(67)$ and $(1234)(56)$ with $o((123)(45)(67)) = 6$ and $o((1234)(56)) = 4$, it follows that $\mathbf{A}_7$ is not a $\Phi$-group. As a consequence, according to Theorem 4.2, we conclude that $\mathcal{S}(\mathbf{S}_5)$ is not a cograph, as required.

4.4.   Sporadic simple groups

Theorem 4.14. For a sporadic simple group $G$, the main supergraph $\mathcal{S}(G)$ is not a cograph.

Proof. It is widely known that there are precisely $26$ sporadic simple groups. Among these, the Mathieu group $M_{11}$ is a subgroup of all but seven sporadic simple groups: the Mathieu group $M_{22}$, the Janko groups $J_i$ ($i = 1, 2, 3$), the Held group $He$, the Rudvalis group $Ru$, and the Thompson group $Th$ (cf. [26]). Using the $\mathbb{ATLAS}$ of finite groups [27], we can see that $M_{11}$ contains a maximal subgroup isomorphic to $\mathbf{S}_5$. By Theorem 4.12, $\mathcal{S}(\mathbf{S_5})$ is not a cograph. Consequently, the main supergraphs of these sporadic simple groups are not cographs, with the exception of $M_{22}$, $J_i$ ($i = 1, 2, 3$), $He$, $Ru$, and $Th$.

In the context of the seven exceptional sporadic simple groups, we examine their properties. According to [27], both $Ru$ and $M_{22}$ contain $\mathbf{A}_7$ as a subgroup, while both $He$ and $Th$ contain $\mathbf{S}_5$. Thus, by Theorems 4.12 and 4.13, the main supergraphs of $M_{22}$, $He$, $Ru$, and $Th$ are not cographs. Additionally, [27] implies that $J_1$, $J_2$, and $J_3$ contain $D_6\times D_{10}$, $\mathbf{A}_5\times D_{10}$, and $\mathbb{Z}_3\times\mathbf{A}_{6}$ as subgroups, respectively. From Theorem 4.6, we conclude that $\mathcal{S}(D_6\times D_{10})$, $\mathcal{S}(\mathbf{A}_5\times D_{10})$, and $\mathcal{S}(\mathbb{Z}_3\times\mathbf{A}_{6})$ are not cographs, leading to the same conclusion for $\mathcal{S}(J_1)$, $\mathcal{S}(J_2)$, and $\mathcal{S}(J_3)$.

4.5.   Small groups

Theorem 4.15. If $G$ is the group with minimal order such that $\mathcal{S}(G)$ is not a cograph, then $G$ must be isomorphic to either $Q_{12}$ or $\mathbb{Z}_{12}$.

Proof. According to Corollary 4.3, the main supergraphs of a $p$-group and a group of order $pq$ are cographs, where $p$ and $q$ ($p\ne q$) are primes. Therefore, $\mathcal{S}(G)$ is a cograph if $|G| < 12$. Now, let us consider groups of an order $12$. It is well-known that there are exactly five groups of order $12$, up to an isomorphism. These are as follows:

By Theorem 4.11, $\mathcal{S}(Q_{12})$ is not a cograph. From Lemma 4.9, we deduce that $\mathcal{S}(\mathbb{Z}_{12})$ is not a cograph. Furthermore, Theorem 4.10 implies that $\mathcal{S}(D_{12})$ is a cograph, while Theorem 4.13 establishes that $\mathcal{S}(\mathbf{A}_4)$ is a cograph. Finally, it follows from Theorem 4.6 that $\mathcal{S}(\mathbb{Z}_2\times \mathbb{Z}_6)$ is a cograph.

In the following, we distinguish a group by using its unique reference number in the SmallGroups Library [28]. Specifically, the $m$th group of the order $n$ is denoted as SmallGroup $(n, m)$. In fact, in GAP [29], $[n, m]$ is used to refer to the GAP ID of the $m$th group of order $n$.

The main supergraphs of a CP-group and a group of order $pq$ are cographs, where $p$ and $q$ are distinct primes. According to Theorem 4.15, most of the small order groups have main supergraphs that are cographs. However, $\mathcal{S}(\mathbb{Z}_{30})$ is not a cograph because $\mathbb{Z}_{30}$ has an element of order $2 \times 3 \times 5$. In the following, we use GAP [29] to classify the finite groups $G$ of order at most 30 such that $\mathcal{S}(G)$ is not a cograph. These groups are presented in Table 1.

Use of AI tools declaration

The authors declare they have not used Artificial Intelligence (AI) tools in the creation of this article.

Acknowledgments

Lin was supported in part by the Special Basic Cooperative Research Programs of Yunnan Provincial Undergraduate University's Association under Grant Nos. 202301BA070001-095 and 202101BA070001-45, Yunnan Provincial Reserve Talent Program for Young and Middle-aged Academic and Technical Leaders under Grant No. 202405AC350086, and the Scientific Research Fund Project of Yunnan Provincial Education Department under Grant Nos. 2023J1213 and 2023J1214.

Conflict of interest

The authors declare there are no conflicts of interest.