Finite groups whose coprime graphs are AT-free

1.   Introduction

In the field of algebraic graph theory, the study of graph representations according to their algebraic structures is a popular and interesting research topic. For example, a well-known graph representation from the algebraic structure group is the Cayley graph, which has a long history of research. On the other hand, graph representations of some algebraic structures have been actively studied in the literature, because of some valuable applications ^[1,2].

One can define a special graph on a group, such as, power graph ^[3] and commuting graph ^[4]. Considering the order of an element in a group is one of the most basic and important concepts in group theory, we may define a graph over a group using its element order. Given a finite group $G$, the coprime graph of $G$, denoted by $\Gamma(G)$, is the undirected graph with vertex set $G$, and two distinct $x, y\in G$ are adjacent if and only if $o(x)$ and $o(y)$ are relatively prime, namely, $(o(x), o(y)) = 1$, where $o(x)$ and $o(y)$ are the orders of $x$ and $y$, respectively. In 2014, the authors ^[5] introduced the concept of a coprime graph of a group. Afterwards, Dorbidi ^[6] proved that for every finite group $G$, the clique number of $\Gamma(G)$ is equal to the chromatic number of $\Gamma(G)$, namely, $\Gamma(G)$ is a weakly perfect graph. Also, Dorbidi ^[6] classified such finite groups whose coprime graph is a complete $r$-partite graph. In 2017, Selvakumar and Subajini ^[7] obtained all finite groups $G$ such that $\Gamma(G)$ is toroidal. In 2021, Hamm and Way ^[8] determined the independence number of the coprime graph on a dihedral group, and they also studied this question: which coprime graphs are perfect? Alraqad et al. ^[9] classified the finite groups whose coprime graph has exactly three end-vertices.

Every graph considered in our paper is undirected without loops and multiple edges. Let $\Gamma$ and $\Delta$ be two graphs. If $\Gamma$ contains no induced subgraph isomorphic to $\Delta$, then $\Gamma$ is called a $\Delta$-free graph. This is equivalent to saying that $\Delta$ is a forbidden subgraph of $\Gamma$. Three independent vertices of a graph form an asteroidal triple if every two of them are connected by a path avoiding the neighborhood of the third one. A simple graph is called asteroidal triple-free (AT-free, for short) if it contains no asteroidal triple ^[10]. The AT-free graphs provide a common generalization of interval, permutation, trapezoid, and cocomparability graphs. In ^[10], Lekkerkerker and Boland demonstrated the importance of asteroidal triples in the theorem: a graph is an interval graph if and only if it is chordal and AT-free. Thus, it appears that the condition of being AT-free prohibits a chordal graph from growing in three directions at once. Later, Golumbic et al. ^[11] showed that cocomparability graphs (and, thus, permutation and trapezoid graphs) are also AT-free. In ^[12], Swathi and Sunitha studied the finite groups whose co-prime graphs are $C_4$-free, claw-free, cographs, split-graphs, and AT-free. Also, they proposed the following question.

Question 1.1. (^[12]) Find a characterization for the finite groups whose coprime graphs are AT-free.

The purpose of this paper is to give a characterization of the finite groups whose coprime graphs are AT-free (see Theorem 2.3). This gives an answer to Question 1.1. As applications, we classify the finite groups $G$ such that $\Gamma(G)$ is AT-free if $G$ is a nilpotent group (see Corollary 2.5), a symmetric group (see Proposition 2.7), an alternating group (see Proposition 2.7), a direct product of two non-trivial groups (see Proposition 2.8), or a sporadic simple group (see Proposition 2.10).

2.   Main results

This section will prove our main results. Every group considered in this paper is finite. For convenience, we always assume that $G$ is a finite group with the identity $e$. Denote by $\pi_e(G)$ and $\pi(G)$ the set of orders of elements of $G$ and the set of prime divisors of $|G|$, respectively. As usual, denote by $\mathbb{Z}_n$ the cyclic group having order $n$. Given a graph, say $\Gamma$, denote by $V(\Gamma)$ and $E(\Gamma)$ the vertex set and edge set of $\Gamma$, respectively. If $\{x, y\}\in E(\Gamma)$, then we also denote this by $x-y$. In a graph, we use $x_1-x_2-\cdots-x_n$ to denote a path of length $n$. The neighborhood of a vertex $x$ in $\Gamma$, denoted by $N(x)$, is the set $\{v\in V(\Gamma): v-x\}$.

We first give two results before giving the proof of our main theorem.

Observation 2.1. (1) Suppose that $\{p_1p_2, p_1p_3, p_1p_4\}\subseteq \pi_e(G)$, where $p_1, p_2, p_3, p_4$ are pairwise distinct primes. Let $a, b, c\in G$ with $o(a) = p_1p_2$, $o(b) = p_1p_3$, and $o(c) = p_1p_4$. Then $a-c^{p_1}-b$ is a path such that $N(c)\cap \{a, c^{p_1}, b\} = \emptyset$, $a-b^{p_1}-c$ is a path such that $N(b)\cap \{a, b^{p_1}, c\} = \emptyset$, and $b-a^{p_1}-c$ is a path such that $N(a)\cap \{b, a^{p_1}, c\} = \emptyset$. As a result, $\{a, b, c\}$ is an AT in $\Gamma(G)$.

(2) Suppose that $\{p_1p_2, p_1p_3, p_2p_3\}\subseteq \pi_e(G)$, where $p_1, p_2, p_3$ are pairwise distinct primes. Let $a, b, c\in G$ with $o(a) = p_1p_2$, $o(b) = p_1p_3$, and $o(c) = p_2p_3$. Then $a-c^{p_2}-c^{p_3}-b$ is a path such that $N(c)\cap \{a, c^{p_2}, c^{p_3}, b\} = \emptyset$, $a-b^{p_1}-b^{p_3}-c$ is a path such that $N(b)\cap \{a, b^{p_1}, b^{p_3}, c\} = \emptyset$, and $b-a^{p_1}-a^{p_2}-c$ is a path such that $N(a)\cap \{b, a^{p_1}, a^{p_2}, c\} = \emptyset$. As a result, $\{a, b, c\}$ is an AT in $\Gamma(G)$.

Lemma 2.2. (^[12]) Let $x, y\in G$. Then $\pi(\langle x\rangle)\subseteq \pi(\langle y\rangle)$ if and only if $N(y) \subseteq N(x)$ in $\Gamma(G)$.

Theorem 2.3. Let $G$ be a finite group. Then $\Gamma(G)$ is ${\rm{AT}}$-free if and only if neither $\{p_1p_2, p_1p_3, p_1p_4\}$ nor $\{p_1p_2, p_1p_3, p_2p_3\}$ is a subset of $\pi_e(G)$ where $p_1, p_2, p_3, p_4$ are pairwise distinct primes.

Proof. The necessity follows trivially from Observation 2.1. We next prove the sufficiency. Suppose that neither $\{p_1p_2, p_1p_3, p_1p_4\}$ nor $\{p_1p_2, p_1p_3, p_2p_3\}$ is a subset of $\pi_e(G)$; here $p_1, p_2, p_3, p_4$ are pairwise distinct primes. Then it is clear that $\pi_e(G)$ has no element, which is a product of three pairwise distinct primes. Assume, to the contrary, that $\Gamma(G)$ has an AT, say $\{x_1, x_2, x_3\}$. If $\pi(\langle x_i\rangle)\subseteq \pi(\langle x_j\rangle)$ for two distinct $i, j\in \{1, 2, 3\}$ and $t\in \{1, 2, 3\}\setminus\{i, j\}$, then by Lemma 2.2, we have that every path from $x_j$ to $x_t$ must contain at least one vertex in $N(x_i)$; this contradicts that $\{x_1, x_2, x_3\}$ is an AT. It follows that $\pi(\langle x_i\rangle)\nsubseteq \pi(\langle x_j\rangle)$ for each two distinct $i, j\in \{1, 2, 3\}$. Since $\{x_1, x_2, x_3\}$ is an independent set of $\Gamma(G)$, it follows that for any $i\in \{1, 2, 3\}$, $o(x_i)$ is not a prime power. As a result, $|\pi(\langle x_i \rangle)| = 2$ for any $i\in \{1, 2, 3\}$.

Now let $\pi(\langle x_1 \rangle) = \{p_1, p_2\}$ where $p_1$ and $p_2$ are distinct primes. Note that $(o(x_1), o(x_2))\ne 1$. We may assume that $\pi(\langle x_2 \rangle) = \{p_i, p_3\}$, where $i = 1$ or $2$ and $p_3$ is a prime, which is different from $p_1$ and $p_2$. Similarly, we also can conclude that $\pi(\langle x_3 \rangle) = \{p_j, p_4\}$, where $j = 1$ or $2$ and $p_4$ is a prime, which is different from $p_1$ and $p_2$. If $p_3 = p_4$, then $i\ne j$, and so $\{p_1p_2, p_1p_3, p_2p_3\}\subseteq \pi_e(G)$, a contradiction. Now assume that $p_3\ne p_4$. Since $(o(x_2), o(x_3))\ne 1$, it must be that $i = j$. It follows that either $\{p_1p_2, p_1p_3, p_1p_4\}\subseteq \pi_e(G)$ or $\{p_1p_2, p_2p_3, p_2p_4\}\subseteq \pi_e(G)$, which is impossible. Consequently, $\Gamma(G)$ is ${\rm{AT}}$-free. The proof is now complete. □

Corollary 2.4. (1) If $|\pi(G)|\le 2$, then $\Gamma(G)$ is ${\rm{AT}}$-free; (2) Let $\pi(G) = \{p_1, p_2, p_3\}$. Then $\Gamma(G)$ is ${\rm{AT}}$-free if and only if $\{p_1p_2, p_1p_3, p_2p_3\}\nsubseteq \pi_e(G)$; (3) If $\Gamma(G)$ is ${\rm{AT}}$-free and $|\pi(G)|\ge 4$, then $Z(G) = \{e\}$.

Recall that a finite group is nilpotent if and only if it is the direct product of its Sylow subgroups. In particular, in a finite nilpotent group, two elements $a, b$ with $(o(a), o(b)) = 1$ must commute. Thus, if $G$ is a nilpotent group such that $\pi(G) = \{p_1, p_2, p_3\}$ for different primes $p_1, p_2, p_3$, then $G$ has elements of order $p_1p_2p_3$. The following result classifies all nilpotent groups whose coprime graphs are ${\rm{AT}}$-free.

Corollary 2.5. Let $G$ be a nilpotent group. Then $\Gamma(G)$ is ${\rm{AT}}$-free if and only if $G = P\times Q$, where $P$ and $Q$ are respectively a $p$-group and a $q$-group for distinct primes $p$ and $q$.

Clearly, for any subgroup $H$ of $G$, $\Gamma(H)$ is an induced subgraph of $\Gamma(G)$. Thus, we have the following result.

Observation 2.6. If $\Gamma(G)$ is ${\rm{AT}}$-free, then $\Gamma(H)$ is also ${\rm{AT}}$-free for any subgroup $H$ of $G$.

The symmetric group of order $n!$, denoted by $\mathbf{S}_n$, is the group consisting of all permutations on $n$ objects. As we know, the symmetric group is important in many different areas of mathematics, including combinatorics and group theory, since every finite group is a subgroup of some symmetric group. In $\mathbf{S}_n$, the set of all even permutations is a group, which is called the alternating group on $n$ objects and is denoted by $\mathbf{A}_n$. Note that $A_n$ is a simple group for any $n\ge 5$.

Proposition 2.7. For symmetric groups and alternating groups, we have the following:

${\rm (1)}$ The graph $\Gamma(\mathbf{S}_n)$ is ${\rm{AT}}$-free if and only if $n\le 7$;

${\rm (2)}$ The graph $\Gamma(\mathbf{A}_n)$ is ${\rm{AT}}$-free if and only if $n\le 8$.

Proof. (1) We first prove that $\Gamma(\mathbf{S}_8)$ is not an ${\rm{AT}}$-free graph. Note that the facts that $o((1, 2)(3, 4, 5)) = 6$, $o((1, 2)(3, 4, 5, 6, 7)) = 10$, and $o((1, 2, 3)(4, 5, 6, 7, 8)) = 15$. As a consequence, we have that $\{6, 10, 15\}\subseteq \pi_e(\mathbf{S}_8)$, and so by Theorem 2.3, $\Gamma(\mathbf{S}_8)$ is not ${\rm{AT}}$-free, as desired. Now by Observation 2.6, it suffices to prove that $\Gamma(\mathbf{S}_7)$ is ${\rm{AT}}$-free. Note that $\pi_e(\mathbf{S}_7) = \{1, 2, 3, 4, 5, 6, 7, 10, 12\}$. Since $\mathbf{S}_7$ has no elements of order $15$, it follows from Theorem 2.3 that $\Gamma(\mathbf{S}_7)$ is ${\rm{AT}}$-free, as desired.

(2) We first prove that $\Gamma(\mathbf{A}_9)$ is not an ${\rm{AT}}$-free graph. Note that the facts that $o((1, 2)(3, 4, 5)(6, 7)) = 6$, $o((1, 2)(3, 4, 5, 6, 7)(8, 9)) = 10$, and $o((1, 2, 3)(4, 5, 6, 7, 8)) = 15$. Thus, we have that $\{6, 10, 15\}\subseteq \pi_e(\mathbf{A}_9)$, which implies that $\Gamma(\mathbf{A}_9)$ is not ${\rm{AT}}$-free by Theorem 2.3, as desired. Now in view of Observation 2.6, it suffices to prove that $\Gamma(\mathbf{A}_8)$ is ${\rm{AT}}$-free. It is easy to check that $\pi_e(\mathbf{A}_8) = \{ 1, 2, 3, 4, 5, 6, 7, 15\}$, so $\pi_e(\mathbf{A}_8)$ has only two elements that are not prime powers. By Theorem 2.3, we have that $\Gamma(\mathbf{A}_8)$ is ${\rm{AT}}$-free, as desired. □

Given a finite group $G$, if any non-trivial element of $G$ is of prime power order, then $G$ is a CP-group ^[13]. For example, for a prime $p$, any $p$-group is also a CP-group. Also, both the symmetric group on four letters and the alternating group of degree five are CP-groups. Given two non-trivial groups $H$ and $K$, for which the direct product $H\times K$ is the coprime graph an ${\rm{AT}}$-free graph? Next, we will characterize the direct products $H\times K$ whose coprime graph is ${\rm{AT}}$-free.

Proposition 2.8. Let $H$ and $K$ be two non-trivial groups. Then $\Gamma(H\times K)$ is ${\rm{AT}}$-free if and only if one of the following holds:

${\rm{(a)}}$ $\pi(H) = \pi(K) = \{p, q\}$, where $p, q$ are distinct primes;

${\rm{(b)}}$ Both $H$ and $K$ are $CP$-groups with $\pi(H) = \{p, q\}$, $\pi(K) = \{r, s\}$, where $p, q, r, s$ are pairwise distinct primes;

${\rm{(c)}}$ One of $H$ and $K$ is a $p$-group; without loss of generality, let $\pi(H) = \{p\}$. Also, $\pi(K)\subseteq\{p, q, r\}$ and $qr\notin \pi_e(K)$, where $p, q, r$ are pairwise distinct primes.

Proof. If (a) occurs, then Corollary 2.4 (1) implies that $\Gamma(H\times K)$ is ${\rm{AT}}$-free. If (b) occurs, then by Theorem 2.3, it is easy to see that $\Gamma(H\times K)$ is ${\rm{AT}}$-free. Now consider (c). If $\pi(K)\subseteq\{p, r\}$ or $\{p, q\}$, then Corollary 2.4 (1) also implies the desired result. Now suppose that $qr\notin \pi_e(K)$, and $\pi(K) = \{p, q, r\}$ or $\{q, r\}$. Then $\pi(H\times K) = \{p, q, r\}$. If $x\in H\times K$ and $o(x)$ is not a prime power, then $\pi(\langle x\rangle) = \{p, q\}$ or $\{p, r\}$. Hence, by Corollary 2.4 (2), we have that $\Gamma(H\times K)$ is ${\rm{AT}}$-free.

Conversely, suppose that $\Gamma(H\times K)$ is ${\rm{AT}}$-free. We next consider two cases.

Case 1. Neither $H$ nor $K$ is a $p$-group for some prime $p$.

We next prove that one of (a) and (b) holds. Firstly, by Theorem 2.3 and the fact that $K$ is not trivial, it is easy to see that $\pi(H)$ has at most $3$ pairwise prime divisors. Assume now that $\pi(H)\subseteq \{p, q, r\}$ for pairwise distinct primes $p, q, r$. We next consider two subcases.

Subcase 1.1. $\pi(H) = \{p, q, r\}$.

Then $\pi(K)\subseteq \{p, q, r\}$; otherwise, the case in Observation 2.1 (2) occurs, and so $\Gamma(H\times K)$ is not ${\rm{AT}}$-free, a contradiction. It follows that there exist at least two distinct prime divisors in $\pi(K)$. Without loss of generality, suppose that $\{p, q\}\subseteq \pi(K)$. Then it must be that $pq, pr, qr\in \pi_e(H\times K)$. It follows from Theorem 2.3 that $\Gamma(H\times K)$ is not ${\rm{AT}}$-free, a contradiction.

Subcase 1.2. $|\pi(H)| = 2$, and without loss of generality, let $\pi(H) = \{p, q\}$.

Suppose that there exists one prime divisor in $\pi(H)\cap \pi(K)$, say $p$. If there exists $r\in \pi(K)\setminus\{p, q\}$, then $pq, rp, rq\in \pi_e(H\times K)$, which is impossible as per Theorem 2.3. It follows that $\pi(K)\subseteq \{p, q\}$. Since $K$ is not a $p$-group, we must have $\{p, q\} = \pi(K)$, and so (a) occurs.

Suppose now that $\pi(H)\cap \pi(K) = \emptyset$. By Theorem 2.3, we clearly have $|\pi(K)|\le 2$. As a result, we can conclude that $|\pi(K)| = 2$ since $K$ is not a primary group. Also, Theorem 2.3 implies that any of $H$ and $K$ can not have elements whose order is the product of two distinct primes. Hence, both $H$ and $K$ are $CP$-groups, and so (b) holds.

Case 2. One of $H$ and $K$ is a $p$-group; without loss of generality, let $\pi(H) = \{p\}$.

In this case, we prove that $(c)$ holds. Clearly, $\pi(K)\setminus \{p\}$ has no three pairwise distinct primes. It follows that $\pi(K)\subseteq\{p, q, r\}$, where $p, q, r$ are pairwise distinct primes. It suffices to show that $qr\notin \pi_e(K)$. If $qr\in \pi_e(K)$, then $\{q, r\}\subseteq\pi(K)$, and so $pq, pr, qr\in \pi_e(H\times K)$, which is a contradiction by Theorem 2.3. Thus, we obtain $qr\notin \pi_e(K)$, and so $(c)$ holds. □

By Proposition 2.8, we have the following examples.

Example 2.9. The graph $\Gamma(G)$ is not ${\rm{AT}}$-free if $G$ is isomorphic to one of the following:

Theorem 2.10. Let $G$ be a sporadic simple group. Then $\Gamma(G)$ is ${\rm{AT}}$-free if and only if $G$ is isomorphic to one of the following Mathieu groups:

Proof. It is well known that there are precisely $26$ sporadic simple groups. We first consider Mathieu groups. For $M_{11}$, we have that $\pi_e(M_{11}) = \{ 1, 2, 3, 4, 5, 6, 8, 11 \}$, and so it is clear that $\Gamma(M_{11})$ is ${\rm{AT}}$-free by Theorem 2.3. For $M_{12}$, one has $\pi_e(M_{12}) = \{ 1, 2, 3, 4, 5, 6, 8, 10, 11 \}$, and so $\Gamma(M_{12})$ is ${\rm{AT}}$-free by Theorem 2.3. For $M_{22}$, we have $\pi_e(M_{22}) = \{ 1, 2, 3, 4, 5, 6, 7, 8, 11\}$, and similarly, $\Gamma(M_{22})$ is ${\rm{AT}}$-free. For $M_{23}$, we have $\pi_e(M_{23}) = \{1, 2, 3, 4, 5, 6, 7, 8, 11, 14, 15, 23\}$, and similarly, $\Gamma(M_{23})$ is ${\rm{AT}}$-free. Note that both $M_{23}$ and $M_{12}$ are subgroups of $M_{24}$ by the $\mathbb{ATLAS}$ of finite groups ^[14]. Hence, we have that $6, 10, 15\in \pi_e(M_{24})$, and so $\Gamma(M_{24})$ is not ${\rm{AT}}$-free by Theorem 2.3.

By ^[14], it follows that Janko group $J_1$, Janko group $J_2$, Janko group $J_4$, Held group $He$, Harada-Norton group $HN$, Thompson group $Th$, Baby Monster group $B$, Monster group $M$, O'Nan group $O'N$, Lyons group $Ly$, Rudvalis group $Ru$, Suzuki group $Suz$, Fischer group $Fi_{22}$, and Higman-Sims group $HS$ contain $D_6\times D_{10}$, $\mathbf{A}_5\times D_{10}$, $M_{24}$, $\mathbf{S}_4\times L_3(2)$, $\mathbf{A}_{12}$, $\mathbf{A}_{9}$, $\mathbf{S}_5\times L_3(2)$, $\mathbf{A}_{12}$, $J_1$, $\mathbf{A}_{11}$, $\mathbb{Z}_2\times \mathbb{Z}_2 \times Sz(8)$, $\mathbf{S}_{3}\times \mathbf{A}_{5}$, $\mathbf{S}_{10}$, and $\mathbf{S}_8$ as subgroups, respectively. By Example 2.9 and Proposition 2.7, we see that the above simple groups do not have ${\rm{AT}}$-free coprime graphs.

Now, note that $\{6, 10, 15\}\in \pi_e(Mcl)\cap \pi_e(J_3)$, and so both $\Gamma(Mcl)$ and $\Gamma(J_3)$ are not ${\rm{AT}}$-free by Theorem 2.3. Now every of $Fi_{23}$ and $Fi_{24}'$ contains $Fi_{22}$ as a subgroup, which implies that the coprime graphs of these two groups are not ${\rm{AT}}$-free. Finally, note that the fact that for each $1\le i \le 3$, the Conway group $Co_i$ has a subgroup isomorphic to $McL$ ^[14]. As a consequence, $\Gamma(Co_i)$ is not ${\rm{AT}}$-free for each $1\le i \le 3$. □

3.   Conclusions

The study of graphical representations of algebraic structures, especially groups, has been an energizing and fascinating research area originating from the Cayley graphs. The coprime graph $\Gamma(G)$ of a finite $G$ is a fairly recent development in the realm of graphs from groups. In this paper, "Forbidden subgraphs of co-prime graphs of finite groups", the authors raised the following question: what is a characterization for the finite groups whose coprime graphs are AT-free? For the above question, in this paper we give a characterization of the finite groups whose coprime graphs are AT-free. As applications, we also classify all finite groups $G$ such that $\Gamma(G)$ is AT-free if $G$ is a nilpotent group, a symmetric group, an alternating group, a direct product of two non-trivial groups, or a sporadic simple group.

Use of AI tools declaration

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

Acknowledgments

The second author was supported by the Shaanxi Fundamental Science Research Project for Mathematics and Physics (Grant No. 22JSQ024).

Conflict of interest

The authors declare there is no conflicts of interest.