Chordality of Enhanced Power Graphs of Finite Simple Groups: A Resolution of a Conjecture

Introduction

For a finite group $G$, the power graph $P(G)$ joins $x,y$ when one lies in the cyclic group generated by the other, and the enhanced power graph $P_E(G)$ joins $x,y$ when $\langle x,y\rangle$ is cyclic; thus $P(G) \subseteq P_E(G)$, with equality if and only if every element has prime-power order (EPPO groups) [1]. A graph is a cograph if it has no induced path $P_4$, and chordal if it has no induced cycle of length $\ge4$.

Forbidden subgraph characterizations provide a powerful structural framework for investigating graphs defined on groups, revealing how the algebraic properties of a group govern the combinatorial structure of its associated graph. Forbidden induced subgraphs in $P(G)$ have been studied by Manna–Cameron–Mehatari [13], Cameron–Manna–Mehatari [4] (simple groups with cograph power graph), Manna–Mehatari [15] and Brachter–Kaja [2] (simple groups with chordal power graph), Manna–Mandal–Lucchini [14] (claw-free power graph); the nilpotent case for $P_E(G)$ is due to Ma–Zahirović–Lv–She [16]. Recently Bubboloni, Fumagalli and Praeger [3] proved that if $P_E(G)$ is a cograph then it is chordal, classified the nonabelian simple groups with cograph $P_E(G)$ (namely $\operatorname{PSL}_2(q)$, $q \ge4$, $\operatorname{PSL}_3(4)$ and $\operatorname{Sz}(q)$), showed that $P_E(\operatorname{Alt}(7))$ is chordal but not a cograph, and posed the problem of determining the simple groups with chordal $P_E(G)$. Moreover, in [7 §7] (see also [17]) the Kourovka problem 21.24 ($P(G)$ cograph $\Rightarrow P(G)$ chordal) is solved, and the conjecture of [3] that $P(G)$ cograph implies $P_E(G)$ cograph is recorded as open.

This paper makes two contributions.

Theorem 1.1 (Classification). Let $G$ be a finite simple group. Then $P_E(G)$ is chordal if and only if $G$ is isomorphic to one of: a cyclic group of prime order; $\operatorname{Alt}(7)$; $\operatorname{PSL}_2(q)$ with $q \ge4$ (this includes $\operatorname{Alt}(5)$, $\operatorname{Alt}(6)$, $\operatorname{PSL}_3(2)$); $\operatorname{Sz}(q)$ with $q=2^{2n+1} \ge8$; $\operatorname{PSL}_3(4)$.

Together with [3] and [7, 17] we obtain, for every finite group $G$,

The principal contribution: By [3 Theorem B], the groups $\operatorname{PSL}_2(q)$, $\operatorname{PSL}_3(4)$, $\operatorname{Sz}(q)$ have cograph, hence chordal, $P_E(G)$, and $\operatorname{Alt}(7)$ is chordal; so the sufficiency half of Theorem 1.1 is already contained in [3] (we include direct proofs for completeness; $\operatorname{Alt}(5)$, $\operatorname{Alt}(6)$, $\operatorname{Alt}(7)$, $\operatorname{PSL}_3(4)$ also follow from [2 Theorem 1.1] and Theorem 1.2). The new content is the necessity: every other simple group has non-chordal $P_E(G)$, which answers the chordal part of Open Problem 1 of [3]; in particular $\operatorname{Alt}(7)$ is the only simple group with chordal but non-cograph $P_E(G)$. Theorem 1.2 proves, for all finite groups, the cograph conjecture of [3], and its chordal version. The converses fail: $P_E(C_{30})$ is complete, whereas $P(C_{30})$ is not chordal (the elements of orders 6, 2, 10, 5, 15, 3 induce a $C_6$, since adjacency in $P(C_{30})$ is divisibility of orders); and $P(\mathbb{Z}_{12})$ is not a cograph (elements 3, 6, 2, 4 of orders 4, 2, 6, 3 induce a $P_4$) while $P_E(\mathbb{Z}_{12})$ is complete. Within simple groups, $\operatorname{PSL}_2(59)$ contains a cyclic subgroup of order 30, so $P(\operatorname{PSL}_2(59))$ is not chordal, while $P_E(\operatorname{PSL}_2(59))$ is chordal (Prop. 4.1).

The negative half rests on one mechanism (Lemma 2.5): commuting elements $x,y$ of coprime prime-power orders with neither $\langle x\rangle$ normal in $C_G(y)$ nor $\langle y\rangle$ normal in $C_G(x)$ yield an induced even cycle; the positive half on a perfect elimination ordering by vertices lying in a unique maximal cyclic subgroup.

Organization: Section 2 collects fundamental concepts and results, Section 3 proves Theorem 1.2, Sections 4 and 5 treat chordal and non-chordal families, Section 6 assembles the proof of Theorem 1.1, and Section 7 records computer checks using GAP 4.12. Section 8 summarizes some well-known results and standard facts.

Preliminary Results

Throughout, we use the symbol $x^c$ to mean $x^c=cxc^{-1}$. We write $x\sim_P y$ if $x\ne y$ and $(x\in\langle y\rangle$ or $y\in\langle x\rangle)$, and $x\sim_E y$ if $x\ne y$ and $\langle x,y\rangle$ is cyclic. If $x\in\langle y\rangle$ then $\langle x,y\rangle=\langle y\rangle$, so $\sim_P\subseteq\sim_E$, and every non-edge of $P_E(G)$ is a non-edge of $P(G)$. We write $A\ntrianglelefteq B$ for “$A$ is not normal in $B$”.

Proof. Adjacency depends only on $\langle x,y\rangle$, giving (a); (b) is the isomorphism theorem and (a). $\square$

Proof. If $\langle x,y\rangle$ is cyclic of prime-power order its subgroups form a chain, so $x\sim_P y$ or $x=y$. Let $C$ be an induced cycle of length $\ge4$ and $x\in C$ of maximal order; its neighbours on $C$ are comparable with $x$ and have order $\le\lvert x\rvert$, so lie in $\langle x\rangle$; subgroups of a cyclic $p$-group form a chain, so they are adjacent, a contradiction. $\square$

Proof. Let $C$ be an induced cycle of length $\ge4$ and $v_i$ its first vertex in the order. Its two neighbours on $C$ lie in $\{v_i,\ldots,v_n\}$ and are non-adjacent, so $v_i$ is not simplicial there.

Proof. Let $\mathcal{X},\mathcal{Y}$ be the sets of $G$-conjugates of $\langle x\rangle,\langle y\rangle$ and choose one generator for each member; these are the vertices of $B$. Two distinct members of $\mathcal{X}$ are non-adjacent because a cyclic group has at most one subgroup of order $r^a$; likewise for $\mathcal{Y}$. A member of $\mathcal{X}$ and one of $\mathcal{Y}$ are adjacent if and only if they commute (commuting elements of coprime orders generate a cyclic group). So $B$ is a bipartite induced subgraph of $\operatorname{PE}(G)$. The vertex $\langle x\rangle$ is adjacent to every $\langle y\rangle^c$ with $c\in C_G(x)$, and there are $|C_G(x):N_{C_G(x)}(\langle y\rangle)|\ge2$ of these; by conjugation every vertex of $\mathcal{X}$ has degree $\ge2$, and symmetrically for $\mathcal{Y}$. A finite graph of minimum degree $\ge2$ has a cycle, a shortest cycle is induced, and in $B$ it has even length $\ge4$.

Proof. $\overline{c}\in C_{\overline{G}}(\overline{y})$ and $\overline{x}^{\overline{c}}\notin\langle\overline{x}\rangle$, so $\langle\overline{x}\rangle\nleq C_{\overline{G}}(\overline{y})$; symmetrically for $\overline{y}$. Apply Lemma 2.5.

Proof. If $\langle y\rangle\le C_G(x)$ then $C_G(x)/(C_G(x)\cap C_G(y))$ embeds in $\operatorname{Aut}(C_s)$, so $|C_G(x):C_G(x)\cap C_G(y)|\le s-1$. But $|C_G(x)\cap C_G(y)|$ divides $g$, so this index is $\ge|C_G(x)|/g$, a contradiction. The same holds for $\langle x\rangle$. Apply Lemma 2.5.

Proof. Take $a,a'\in A$ of order $r$ and $b,b'\in B$ of order $s$ with $\langle a\rangle\ne\langle a'\rangle$, $\langle b\rangle\ne\langle b'\rangle$. Then $a\nsim a'$ and $b\nsim b'$, while every cross pair commutes and has coprime orders, hence is adjacent. So $(a,b,a',b')$ is an induced $C_4$.

The lifting theorem

Proof of Theorem 1.2. We prove the contrapositive: if $\operatorname{PE}(G)$ contains an induced cycle of length $\ge4$ (resp. an induced $P_4$), so does $P(G)$.

Let $\Gamma$ be an induced subgraph of $\operatorname{PE}(G)$ that is a cycle $v_1,\ldots,v_k$ ($k\ge4$, indices mod $k$) or a path $v_1,\ldots,v_k$ ($k\ge4$), with edges $e_i=v_iv_{i+1}$. Being induced and of length $\ge4$, $\Gamma$ has no triangle. Step 1. Let $I$ be the set of $i$ such that $e_i$ is an edge of $\Gamma$ but $v_i \not\sim_P v_{i+1}$. For $i \in I$ let $z_i$ generate the cyclic group $\langle v_i,v_{i+1}\rangle$; then $v_i,v_{i+1} \in\langle z_i\rangle$.

Step 2 (key observation (K)). Let $i \in I$ and let $w$ be a vertex of $\Gamma$. If $w \in\langle z_i\rangle$ or $z_i \in\langle w\rangle$, then $w \in\{v_i,v_{i+1}\}$.

Indeed, if $w \in\langle z_i\rangle$ then $\langle w,v_i\rangle$ and $\langle w,v_{i+1}\rangle$ lie in the cyclic group $\langle z_i\rangle$; if $z_i \in\langle w\rangle$ then $v_i,v_{i+1} \in\langle w\rangle$ and both groups equal $\langle w\rangle$. In either case $w$ equals or is $\sim_E$-adjacent to each of $v_i,v_{i+1}$. If $w \notin\{v_i,v_{i+1}\}$ this is a triangle in $\Gamma$, which is impossible.

Step 3 (consequences).

• (a) $z_i \notin V(\Gamma)$: if $z_i=v_j$ then $v_j \in\langle z_i\rangle$, so by (K) $v_j \in\{v_i,v_{i+1}\}$; but $z_i \in\{v_i,v_{i+1}\}$ would give $v_i \sim_P v_{i+1}$, contradicting $i \in I$.

• (b) For $i \ne j$ in $I$, $z_j \notin\langle z_i\rangle$ (in particular $z_i \ne z_j$ and $z_i \not\sim_P z_j$): if $z_j \in\langle z_i\rangle$ then $v_j,v_{j+1} \in\langle z_j\rangle\le\langle z_i\rangle$, so by (K) $\{v_j,v_{j+1}\}=\{v_i,v_{i+1}\}$ and $j=i$.

• (c) For $i \in I$ and a vertex $v_j$ of $\Gamma$: $z_i \sim_P v_j$ if and only if $j \in\{i,i+1\}$. The “if” holds as $v_j \in\langle z_i\rangle$; the “only if” is (K).

Step 4. Let $\Gamma'$ arise from $\Gamma$ by replacing, for every $i \in I$, the edge $v_iv_{i+1}$ by the path $v_i,z_i,v_{i+1}$. By (a),(b) its vertices are distinct, and it is a cycle (resp. path) of length $\ge k \ge4$. We claim $\Gamma'$ is an induced subgraph of $P(G)$.

• Its edges are $\sim_P$-edges: $v_iz_i$, $z_iv_{i+1}$ by (c); $e_i$ for $i \notin I$ by definition of $I$.

• A pair $v_jv_l$ that is not an edge of $\Gamma'$ is non-adjacent in $\Gamma$ (hence in $P_E(G)$, hence in $P(G)$), or equals $v_iv_{i+1}$ with $i \in I$ (non-adjacent in $P(G)$ by definition of $I$).

• A pair $z_iv_j$ that is not an edge has $j \notin\{i,i+1\}$ and is non-adjacent by (c).

• $z_iz_j$ ($i \ne j$) is non-adjacent by (b).

Step 5. If $\Gamma$ is an induced cycle, $\Gamma'$ is an induced cycle of length $\ge4$ in $P(G)$. If $\Gamma$ is an induced $P_4$, $\Gamma'$ is an induced path on $\ge4$ vertices of $P(G)$ and any four consecutive vertices induce a $P_4$.

Simple groups with chordal $P_E(G)$

The following facts are used; sources are listed in § 8.

Proposition 4.1 (PSL$_2(q)$, $q \ge4$). $P_E(\operatorname{PSL}_2(q))$ is chordal, and in fact $P_E(\operatorname{PSL}_2(q))-\{1\}$ is a disjoint union of cliques; in particular $P_E(\operatorname{PSL}_2(q))$ is a cograph (cf. [3]).

Proof. Facts D (§ 8). Let $A$ be a Sylow $p$-subgroup ($q=p^f$); $C(a)=A$ for $a \in A^\#$. $q$ even. All involutions lie in Sylow 2-subgroups, and the tori have odd orders $q \pm1$. Every $u \ne1$ is a 2-element, in $A$, or lies in a torus $T$ with $C(u)=T$. $q$ odd. For an involution $z$, $C(z)$ is dihedral of order $q-\varepsilon$ ($q \equiv\varepsilon\pmod{4}$), $z$ is its central involution and the rotation subgroup $R$ is cyclic of even order $m=(q-\varepsilon)/2$.

We show every $u \ne1$ lies in a unique maximal cyclic subgroup $M(u)$:

• $u \in A$: a cyclic subgroup containing $u$ lies in $C(u)=A$, so has order $p$ and $M(u)=\langle u\rangle$.

• $|u| \ge2$ and $p \nmid|u|$: a cyclic subgroup containing $u$ lies in $C(u)=T$, so $M(u)=T$.

• $u=z$ an involution, $q$ odd: a cyclic subgroup containing $z$ lies in $C(z)$. If $m \ge4$ a reflection is not central, so it lies in $R$ and $M(z)=R$. If $m=2$ ($q=5$) then $C(z) \cong V_4$ and $M(z)=\langle z\rangle$.

If $\langle u,h\rangle$ is cyclic it lies in a maximal cyclic subgroup, which then equals $M(u)$ and $M(h)$; so $u \sim_E h \Longleftrightarrow M(u)=M(h)$, and $P_E-\{1\}$ is a disjoint union of cliques. Apply Lemma 2.2.

Proof. Facts S. Let $P$ be a Sylow 2-subgroup, $Z=Z(P)=\Omega_1(P)$.

Odd order. If $|u|$ is odd, neighbours of $u$ lie in $C(u)=T$, a cyclic torus, so $N[u]=T$ is a clique.

Involution $z\in Z$ (note $C(z)=P$ for every involution $z\in Z$, and all involutions lie in $Z$). A neighbour $h$ lies in $P$. If $|h|=2$ and $h\neq z$ then $\langle z,h\rangle\cong V_4$ is not cyclic. If $|h|=4$ then $h^2$ is the unique involution of $\langle z,h\rangle$, so $h^2=z$.

Element $w$ of order 4. A neighbour lies in $C(w)=\langle w\rangle Z$, so is $h=w^i z'$ with $z'\in Z$ and $\langle w,h\rangle=\langle w,z'\rangle$; if $z'\notin\langle w^2\rangle$ this contains $V_4$. So $N[w]=\langle w\rangle$.

Hence $P_E(\operatorname{Sz}(q))-\{1\}$ is the disjoint union of the cliques given by the tori (minus 1) and the components $\{z\}\cup\{h:h^2=z\}$, each a union of triangles $\{z,w,w^{-1}\}$ sharing the cut vertex $z$. Every block is a clique, so there are no induced cycles of length $\geq4$; apply Lemma 2.2. (Note that $P_E(\operatorname{Sz}(q))$ itself contains diamonds $\{1,z,w,w'\}$ with $w^2={w'}^2=z$, $\langle w\rangle\neq\langle w'\rangle$; the block statement refers to $P_E-\{1\}$.)

Proof. The element orders of $\operatorname{PSL}_3(4)$ are $1,2,3,4,5,7$ (ATLAS), so it is EPPO; apply Lemma 2.3.

Proof. The element orders are $1,\ldots,7$ with 4, 5, 6, 7 occurring. A cyclic overgroup of an element of order 4, 5, 6 or 7 has order a multiple of it and at most 7, so equal to it; thus such elements lie in a unique maximal cyclic subgroup, are simplicial (Lemma 2.4), and may be removed first.

All involutions of $\operatorname{Alt}(7)$ are conjugate to $z=(12)(34)$, and $C_{\operatorname{Alt}(7)}(z)=\frac{1}{2}|C_{\operatorname{Sym}(7)}(z)|=\frac{1}{2}|D_8\times\operatorname{Sym}\{5,6,7\}|=24$ has Sylow 3-subgroup $\langle(567)\rangle$ (a subgroup of order 3 of $D_8\times\operatorname{Sym}\{5,6,7\}$ lies in $\operatorname{Sym}\{5,6,7\}$, where it is unique). In the remaining graph $N[z]=\{1,z,u,u^2\}$ with $u=(567)$, which is a clique ($\langle zu\rangle$ is cyclic of order 6); so $z$ is simplicial and all involutions may be removed. What remains is $\{1\}$ together with the subgroups of order 3, triangles through 1; these eliminate in turn. By Lemma 2.4, $P_E(\operatorname{Alt}(7))$ is chordal.

Simple groups with non-chordal $P_E(G)$

Alternating groups

Proof. $\operatorname{Sym}(6)$: take $x=(123)$, $y=(45)$. Then $C(x)=\langle x\rangle\times\operatorname{Sym}\{4,5,6\}$ contains $(46)$, which moves $\langle y\rangle$, and $C(y)=\langle y\rangle\times\operatorname{Sym}\{1,2,3,6\}$ contains $(16)$ with $x^{(16)}=(623)\notin\langle x\rangle$. Lemma 2.5.

$\operatorname{Alt}(8)$: take $x=(123)$, $y=(45)(67)$. Then $C_{\operatorname{Alt}(8)}(x)=\langle x\rangle\times\operatorname{Alt}\{4,\ldots,8\}$ contains $y\in\operatorname{Alt}(5)$ and $\langle y\rangle$ is normal in the simple group $\operatorname{Alt}(5)$. Also $c=(18)(45)\in\operatorname{Alt}(8)$ commutes with $y$ and $x^c=(823)\notin\langle x\rangle$. Lemma 2.5.

Larger $n$: Lemma 2.1(a).

Linear groups

Let $E_{ij}$ denote matrix units.

Proof. Put $y=I+E_{12}$, $c=I+E_{13}$, $c'=I+E_{21}$ and choose $x$ as follows.

• $q$ odd: $x=\operatorname{diag}(-1,-1,1)$, of order $2$; $x\notin Z_0$ since $|Z(\mathrm{SL}_3(q))|$ divides $3$, so $\bar{x}$ has order $2$; $|\bar{y}|=p$ is odd.

• $q=2^f\ge8$: $q-1\equiv7\pmod{8}$ while $3^k\equiv1,3\pmod{8}$, so $q-1$ has a prime divisor $r\ne3$. Take $a\in\mathbb{F}_q^\times$ of order $r$ and $x=\operatorname{diag}(a,a,a^{-2})$. Then $a^3\ne1$, so $x$ is not scalar, $\bar{x}$ has order $r$, and $|\bar{y}|=2$.

Then $x$ commutes with $y$ and $c'$ (its first two diagonal entries are equal), and $c\in C(y)$ because $E_{12}E_{13}=E_{13}E_{12}=0$. Further $cxc^{-1}=x+(x_{33}-x_{11})E_{13}$ with $x_{33}\ne x_{11}$ is not diagonal, so $x^c\notin\langle x\rangle Z_0$, a group of diagonal matrices. And $y^{c'}=I-E_{11}+E_{22}+E_{12}-E_{21}$ has non-zero $(2,1)$ entry, whereas every element of $\langle y\rangle Z_0$ is a scalar multiple of $I+kE_{12}$. Lemma 2.6 applies.

Proof. $n=3$ is Lemma 5.2. Let $n\ge4$ and $Z=\{\lambda I:\lambda^n=1\}$.

• $q\ne2,4$: the block $H=\mathrm{SL}_3(q)\oplus I_{n-3}$ meets $Z$ trivially (a scalar in $H$ is $1$ on the identity block); Lemmas 5.2 (with $Z_0=1$) and 2.1(b).

• $q=4$: $H=(\mathrm{SL}_2(4)\times\mathrm{SL}_2(4))\oplus I_{n-4}\cong\operatorname{Alt}(5)\times\operatorname{Alt}(5)$ meets $Z$ trivially (a scalar $\lambda$ in a block $\mathrm{SL}_2(4)$ has $\lambda^2=1$, so $\lambda=1$); Lemmas 2.8, 2.1(b).

• $q=2$: $\mathrm{PSL}_n(2)=\mathrm{SL}_n(2)\supseteq\mathrm{SL}_4(2)\cong\operatorname{Alt}(8)$; Prop. 5.1.

Symplectic groups

Let $e_1,f_1,e_2,f_2$ be a symplectic basis with $B(e_i,f_i)=1=-B(f_i,e_i)$, and $T_u:v\mapsto v+B(v,u)u$ a symplectic transvection; then $gT_ug^{-1}=T_{gu}$ and $T_{-u}=T_u$.

Proof. $q=2$: Prop. 5.1.

$q$ odd. Let $x=-1$ on $W_1=\langle e_1,f_1\rangle$ and $+1$ on $W_2=\langle e_2,f_2\rangle$; $y=T_{e_1}$, $c=T_{e_1+e_2}$, $c'=T_{f_1}$, $Z=\{\pm1\}$. Since $xT_ux^{-1}=T_{xu}$ and $T_{-u}=T_u$ we get $[x,y]=[x,c']=1$; $ce_1=e_1$ as $B(e_1,e_1+e_2)=0$, so $c\in C(y)$. Further $cf_1=f_1+B(f_1,e_1+e_2)(e_1+e_2)=f_1-(e_1+e_2)\notin W_1\cup W_2$, so the $(-1)$-eigenspace $c(W_1)$ of $x^c$ is neither $W_1$, $W_2$ nor $0,V$; hence $x^c\notin\{\pm1,\pm x\}$. Finally $c'e_1=e_1+B(e_1,f_1)f_1=e_1+f_1$, so $y^{c'}=T_{e_1+f_1}$ is a non-trivial unipotent element with image line $\langle e_1+f_1\rangle\ne\langle e_1\rangle$, while the unipotent elements of $\langle y\rangle Z$ are $1$ or have image line $\langle e_1\rangle$. So $y^{c'}\notin\langle y\rangle Z$. The elements $x,y$ have orders $2,p$. By Lemma 2.6 with $Z$, $\mathrm{PSp}_4(q)$ is non-chordal. The same computation shows $x^c\notin\{1,x\}$ and $y^{c'}\notin\langle y\rangle$, so Lemma 2.6 with $Z=1$ shows that $\mathrm{Sp}_4(q)$ itself is non-chordal.

$q$ even, $q\ge4$. $\mathrm{Sp}_4(q)\supseteq\mathrm{SL}_2(q)\times\mathrm{SL}_2(q)$ with simple factors, and the centre is trivial. Lemma 2.8 with $r=2$ and an odd prime $s\mid q+1$.

Proof. $H=\mathrm{Sp}_4(q)\oplus I_{2m-4}$ meets the centre $\{\pm1\}$ trivially (as $-1$ is non-trivial on the identity block, of dimension $2m-4\ge2$). By Prop. 5.4, $H\cong\mathrm{Sp}_4(q)$ is non-chordal for every $q$ (including $q=2$, where $\mathrm{Sp}_4(2)\cong\operatorname{Sym}(6)$); apply Lemma 2.1(b).

Unitary groups

We use the Hermitian form with Gram matrix $J=\operatorname{antidiag}(1,1,1)$ on $\mathbb{F}_{q^2}^3$; bars denote $\lambda\mapsto\lambda^q$. The direct computation of $\bar{g}^{T}Jg=J$ gives:

• $\begin{pmatrix} 1 & \alpha& \beta\\ 0 & 1 & -\bar{\alpha} \\ 0 & 0 & 1 \end{pmatrix} \in\operatorname{SU}_3(q)$ if and only if $\beta+\bar{\beta}+\alpha\bar{\alpha}=0$; these form a group $U$ of order $q^3$ with centre $\{I+tE_{13}:t+\bar{t}=0\}$;

• $I+sE_{31}\in\operatorname{SU}_3(q)$ if and only if $s+\bar{s}=0$;

• $\operatorname{diag}(a,b,a')\in\operatorname{SU}_3(q)$ if and only if $b\bar{b}=1$, $a'=\bar{a}^{-1}$ and $aba'=1$.

Proof. Let $Z=Z(\operatorname{SU}_3(q))$, of order $\gcd(3,q+1)$; the case $Z=1$ gives $\operatorname{SU}_3(q)$. Choose $a\in\mathbb{F}_{q^2}^{\times}$ with $a^{q+1}=1$, $a^3\ne1$ and of prime-power order:

• $q$ odd: $a=-1$;

• $q$ even, $q+1$ has a prime divisor $r\ne3$: $a$ of order $r$;

• $q$ even, $q+1=3^k$: by Mihăilescu’s theorem $q=8$; take $a$ of order $9$ (then $x^3=a^3I\in Z$ and $\bar{x}$ has order $3$).

In every case $a\ne a^{-2}$ (as $a^3\ne1$), so $x=\operatorname{diag}(a,a^{-2},a)\in\operatorname{SU}_3(q)$ is not scalar and $\bar{x}\ne1$. Put $y=I+tE_{13}$ with $t\ne0$, $t+\bar{t}=0$; $|y|=p$ is coprime to $|\bar{x}|$ (for $q$ odd $|x|=2$; for $q$ even $|y|=2$ and $|\bar{x}|$ is odd). Clearly $[x,y]=1$.

Take $c\in U$ with $\alpha\ne0$ (exists since the trace $\mathbb{F}_{q^2}\to\mathbb{F}_q$ is onto). As $E_{13}$ is central in $U$, $c\in C(y)$. The $(1,2)$ entry of $cxc^{-1}-x$ is $\alpha(a^{-2}-a)\ne0$, so $xc$ is not diagonal and $x^c\notin\langle x\rangle Z$.

Take $c'=I+sE_{31}$ with $s\ne0$, $s+\bar{s}=0$; it commutes with $x$ since $x_{11}=x_{33}$, and

has $(3,1)$ entry $-ts^2\ne0$, while every element of $\langle y\rangle Z$ has $(3,1)$ entry 0. Apply Lemma 2.6.

Proof. $q\geq3$: the block $\operatorname{SU}_3(q)\oplus I_{n-3}$ meets the centre (scalars) trivially; Prop. 5.6, Lemma 2.1(b). $q=2$, $n=4$: $Z(\operatorname{SU}_4(2))=1$ and $\operatorname{PSU}_4(2)\cong\operatorname{PSp}_4(3)$, non-chordal by Prop. 5.4. $q=2$, $n\geq5$: block $\operatorname{SU}_4(2)\oplus I_{n-4}$.

Orthogonal groups

Let $O$ be the full isometry group of the quadratic form, and $\Omega\leq O$ the usual subgroup: for $n\geq5$ the derived subgroup of $O$; equivalently the kernel of the spinor norm and determinant ($q$ odd), resp. of the Dickson invariant ($q$ even). In all cases $O/\Omega$ is abelian (of order $\leq4$), so $\Omega$ contains every perfect subgroup of $O$.

Proof. $q\ne2,4$. Write the space as $U\oplus U^*\oplus W$ with $U$ totally singular of dimension $k\geq3$ ($k=n$, $\dim W=1$ for $\Omega_{2n+1}$; $k=n$, $W=0$ for the $+$ type; $k=n-1$, $W$ an anisotropic $2$-space, for the $-$ type). The map $g\mapsto g\oplus g^{-T}$ embeds $\operatorname{SL}_3(q)\leq\operatorname{SL}_k(q)$ (acting on the first three coordinates of $U$) into $O$; the image $H\cong\operatorname{SL}_3(q)$ is perfect, so $H\leq\Omega$. $H$ acts trivially on a non-zero subspace, so $H$ meets the centre of $\Omega$ ($\subseteq\{\pm1\}$) trivially. By Lemma 5.2 with $Z_0=1$ and Lemma 2.1(b), $G$ is non-chordal. (For $q$ odd and type $2n+1$ the centre is trivial.)

$q \in\{2,4\}$. For $\Omega_{2n+1}(q) \cong\operatorname{Sp}_{2n}(q)$ use Prop. 5.5. For $\Omega^\pm_{2n}(q)$, the stabilizer in $O^\pm_{2n}(q)$ of a non-singular vector $v$ is $\operatorname{Sp}_{2n-2}(q) \times\langle r_v\rangle$ ($r_v$ the transvection with centre $v$, which fixes $v$ as $q$ is even). The factor $\operatorname{Sp}_{2n-2}(q)$ is perfect since $2n-2 \ge6$, so it lies in $\Omega$; it is non-chordal by Prop. 5.5. The centre is trivial for $q$ even. □

Exceptional groups and the Tits group

Proof. ${}^2G_2(q)$, $q \ge27$. By Facts W, an involution $x$ has $|C(x)| = q(q^2-1)$ with $C(x) \cong C_2 \times\operatorname{PSL}_2(q)$; $C(x)$ contains an element $y$ of order 3 (as $3 \mid q$), and $|C(y)| \in\{q^2,2q^2\}$. Then $g = \gcd(|C(x)|,|C(y)|) \in\{q,2q\}$, so $|C(x)|/g \ge(q^2-1)/2 > 2$ and $|C(y)|/g \ge q > 1$. Lemma 2.7.

Containments (sources in Table 1): $G_2(q) \supseteq\operatorname{SU}_3(q)$ for $q \ge3$, and $G_2(2)' \cong\operatorname{PSU}_3(3)$ (ATLAS); ${}^3D_4(q) \supseteq G_2(q)$; the Tits group contains $L_3(3):2 \supseteq\operatorname{SL}_3(3) = \operatorname{PSL}_3(3)$ (non-chordal by Lemma 5.2 as $3 \ne2,4$) and ${}^2F_4(q) \supseteq{}^2F_4(2)'$ (subfield subgroup); $F_4(q)$ contains the subgroup generated by long-root subgroups of a subsystem of type $A_2$, which is $\operatorname{SL}_3(q)/Z_0$ for some $Z_0 \le Z(\operatorname{SL}_3(q))$, non-chordal for $q \ne2,4$ by Lemma 5.2, whichever $Z_0$ occurs; for $q$ even $F_4(q) \supseteq B_4(q) \cong\operatorname{Sp}_8(q)$, non-chordal by Prop. 5.5, which covers $q=2,4$. For $G \in\{E_6(q),{}^2E_6(q),E_7(q),E_8(q)\}$ (simple versions), let $\widetilde{G}$ be the corresponding simply connected group; it contains a subgroup $H \cong F_4(q)$ [2] (Dynkin sub-diagram of type $F_4$ for $E_k$, via $E_6 \le E_7 \le E_8$, and, for ${}^2E_6$, as the fixed points of the graph automorphism) and $G = \widetilde{G}/N$ with $N$ central. Since $F_4(q)$ is simple non-abelian, $H \cap N = 1$, so $H$ embeds in $G$ (Lemma 2.1(b)); $H$ is non-chordal by the $F_4$ case. In all cases Lemma 2.1(a) transfers non-chordality to $G$. □

Sporadic groups

Proof. Centralizer orders and class data below are checked with the GAP Character Table Library (§ 7).

• $M_{11}$: a class $6A$ with $x=g^3 \in2A$, $y=g^2 \in3A$, $|C(x)|=48$, $|C(y)|=18$, $\gcd=6$; $48/6=8>2$, $18/6=3>1$. Lemma 2.7.

• $M_{22}$: $|C(2A)|=384$, $|C(3A)|=36$, $\gcd=12$; $32>2$, $3>1$. Lemma 2.7.

• $J_3$: the only class of elements of order 6 is $6A$, with $g^3 \in2A$, $g^2 \in3A$, $|C(2A)|=1920$, $|C(3A)|=1080$, $\gcd=120$; $16>2$, $9>1$. Lemma 2.7.

@-end- төхөөр

• $J_1$: here $|C(2A)| = 120$, $|C(3A)| = 30$ and $\gcd= 30$, so $|C(y)|/\gcd= 1 \ne1$ and Lemma 2.7 fails; we use Lemma 2.5 instead. $C(2A) = 2 \times\operatorname{Alt}(5)$ and $C(3A) = 3 \times D_{10}$. Take $y \in3A$ and an involution $x \in C(y)$ (which lies in $D_{10}$ and is non-central there), so $\langle x\rangle\nsubseteq C(y)$; and $y \in C(x) = 2 \times\operatorname{Alt}(5)$ lies in the simple factor, so $\langle y\rangle\nsubseteq C(x)$.

• $J_2 \supseteq\operatorname{Alt}(4) \times\operatorname{Alt}(5)$ and $He \supseteq S_4 \times\operatorname{PSL}_3(2)$ (maximal subgroups): Lemma 2.8.

• $Ru \supset{}^2F_4(2)'.2 \supset{}^2F_4(2)'$ and $Th \supset\operatorname{PSL}_3(3)$ (maximal subgroups): Prop. 5.9, Lemma 2.1(a).

• Each of the remaining 19 groups (including $M_{11}$ itself) contains $M_{11}$; see Table 2.

Group $G$	Containment chain
$M_{11}$	itself
$M_{12}$, $M_{23}$, $HS$, $McL$, $O'N$, $B$	$M_{11} \leq G$ (library class fusion)
$M_{24}$	$M_{11} \leq M_{23} \leq M_{24}$
$Co_2$, $Co_3$	$M_{11} \leq M_{23} \leq G$
$Co_1$	$M_{11} \leq M_{23} \leq Co_2 \leq Co_1$
$Suz$, $HN$	$M_{11} \leq M_{12} \leq M_{12}.2 \leq G$
$Fi_{22}$	$M_{11} \leq M_{12} \leq Fi_{22}$
$Fi_{23}$	$M_{11} \leq Fi_{22}$ lifts to $2.Fi_{22} \leq Fi_{23}$
$Fi'_{24}$	$M_{11} \leq Fi_{23} \leq Fi'_{24}$
$Ly$	$M_{11} \leq McL$ lifts to $3.McL:2 \leq Ly$
$M$	$M_{11} \leq B$ lifts to $2.B \leq M$
$J_4$	$M_{11} \leq M_{24} \leq2^{11}\!:\!M_{24} \leq J_4$

Proof of Theorem 1.1

By the classification of finite simple groups, $G$ is cyclic of prime order, alternating, of Lie type, or sporadic. Table 3 accounts for every family exactly once, including the isomorphisms with small cases and the non-simple small groups that must be excluded.

Family	$P_E$ chordal?	Reference / remark
$C_p$	yes	complete graph
$\operatorname{Alt}(5), \operatorname{Alt}(6)$	yes	$\cong\operatorname{PSL}_2(4)=\operatorname{PSL}_2(5)$, $\operatorname{PSL}_2(9)\cong\operatorname{Sp}_4(2)'$
$\operatorname{Alt}(7)$	yes	Prop. 4.4
$\operatorname{Alt}(n),\ n\geq8$	no	Prop. 5.1; $\operatorname{Alt}(8)\cong\operatorname{PSL}_4(2)$
$\operatorname{PSL}_2(q),\ q\geq4$	yes	Prop. 4.1; $\operatorname{PSL}_2(7)\cong\operatorname{PSL}_3(2)$, $\operatorname{PSL}_2(8)\cong{}^2G_2(3)'$; ($\operatorname{PSL}_2(2),\operatorname{PSL}_2(3)$ not simple)
$\operatorname{PSL}_3(2)$	yes	$\cong\operatorname{PSL}_2(7)$
$\operatorname{PSL}_3(4)$	yes	Prop. 4.3
$\operatorname{PSL}_3(q),\ q\neq2,4$	no	Lemma 5.2
$\operatorname{PSL}_n(q),\ n\geq4$	no	Prop. 5.3
$\operatorname{PSU}_3(q),\ q\geq3$	no	Prop. 5.6; $\operatorname{PSU}_3(3)\cong G_2(2)'$; ($\operatorname{PSU}_3(2)$ not simple)
$\operatorname{PSU}_n(q),\ n\geq4$	no	Prop. 5.7; $\operatorname{PSU}_4(q)\cong\operatorname{P\Omega}_6^-(q)$
$\operatorname{PSp}_4(q),\ q\geq3$	no	Prop. 5.4; $\Omega_5(q)\cong\operatorname{PSp}_4(q)$
$\operatorname{PSp}_4(2)'\cong\operatorname{Alt}(6)$	yes	counted under $\operatorname{PSL}_2(9)$
$\operatorname{PSp}_{2m}(q),\ m\geq3$	no	Prop. 5.5
$\Omega_{2n+1}(q)\ (n\geq3),\ \operatorname{P\Omega}_{2n}^{\pm}(q)\ (n\geq4)$	no	Prop. 5.8
$\operatorname{P\Omega}_3(q),\ \operatorname{P\Omega}_4^-(q)$	yes	$\cong\operatorname{PSL}_2(q),\operatorname{PSL}_2(q^2)$
$\operatorname{P\Omega}_6^+(q)$	no	$\cong\operatorname{PSL}_4(q)$
$\operatorname{Sz}(q),\ q\geq8$	yes	Prop. 4.2; ($\operatorname{Sz}(2)$ not simple)
${}^2G_2(q),\ q\geq27$	no	Prop. 5.9; ${}^2G_2(3)'\cong\operatorname{PSL}_2(8)$
$G_2(q),\ {}^3D_4,\ F_4,\ {}^2F_4(q),\ {}^2F_4(2)',\ E_6,\ {}^2E_6,\ E_7,\ E_8$	no	Prop. 5.9; $G_2(2)'\cong\operatorname{PSU}_3(3)$
26 sporadic groups	no	Prop. 5.10

The groups with chordal $P_E$ are therefore exactly $C_p$, $\operatorname{Alt}(7)$, $\operatorname{PSL}_2(q)$ ($q \geq4$), $\operatorname{Sz}(q)$ ($q \geq8$) and $\operatorname{PSL}_3(4)$.

Remark 6.1. Comparison with [2]: $P(G)$ is chordal for simple $G$ if and only if $G$ is $C_p$, $\operatorname{Alt}(5)$, $\operatorname{Alt}(6)$, $\operatorname{Alt}(7)$, $\operatorname{PSL}_3(4)$, or $\operatorname{PSL}_2(q)$, $\operatorname{Sz}(q)$ subject to arithmetic conditions: $(q \mp1)/\gcd(q \mp1,2)$ for $\operatorname{PSL}_2(q)$, resp. $q - 1$ and $q \pm2^{n+1} + 1$ for $\operatorname{Sz}(q)$, each have at most two prime divisors and at most one prime divisor of multiplicity $> 1$. By Theorem 1.2 that list is contained in ours; the arithmetic conditions disappear for $P_E$ because in $\operatorname{PSL}_2(q)$ distinct maximal cyclic subgroups intersect trivially (Prop. 4.1) and in $\operatorname{Sz}(q)$ they intersect in at most an involution.

Computational verification

All checks are performed with GAP 4.12 (see [9]) (with the CTblLib package) and Python/NetworkX. Chordality of $P_E(G)$ is tested by listing all cyclic subgroups of $G$ (so that $P_E(G)$ is the union of the cliques they span).

• $P_E(G)$ is chordal for $G = \operatorname{PSL}_2(q)$ with $q \in\{4, 5, 7, 8, 9, 11, 13, 16, 17, 19, 23, 25, 27, 29, 31\}$, $G = \operatorname{Alt}(6)$, $\operatorname{Alt}(7)$ and $\operatorname{PSL}_3(4)$ (order 20160).

• $P_E(G)$ is non-chordal for $G=\operatorname{PSL}_3(3)$, $\operatorname{PSU}_3(3)$, $\operatorname{Alt}(8)$ and $M_{11}$ (same method), in agreement with the proofs above.

• The ATLAS data used in Proposition 5.10 (classes, centralizer orders, class 6A and its powers for $M_{11},M_{22},J_1,J_3$) are read from the GAP Character Table Library; the class fusions for the containments in Table 2 and in the proofs for $Ru,Th,J_2$ and the Tits group are confirmed there, and the maximal subgroups $S_4\times\operatorname{PSL}_3(2)\leq He$ and $L_3(3)\leq Th$ are confirmed from the library’s list of maximal subgroups.

• Chordality for $\operatorname{Sz}(8)$, $\operatorname{PSp}_4(3)$, $\operatorname{PSU}_3(4)$ and the larger $\operatorname{PSL}_2(q)$; the containments in Table 1 and $2^{11}\!:\!M_{24}\leq J_4$, taken from the cited literature and ATLAS.

Containment	Source
$SU_3(q) \le G_2(q)$ ($q \ge3$), $PSU_3(3) \cong G_2(2)'$	Kleidman (odd $q$), Cooperstein ($q$ even), ATLAS
$G_2(q) \le{}^3D_4(q)$	Kleidman (Steinberg triality groups)
$L_3(3):2 \le{}^2F_4(2)'$	ATLAS; Wilson §4.9
${}^2F_4(2) \le{}^2F_4(q)$, $q = 2^{2n+1}$	Malle (subfield subgroups)
$A_2(q) \le F_4(q)$	Gorenstein–Lyons–Solomon, Prop. 2.6.2; Brachter–Kaja, Lemma 2.3
$B_4(q) \cong Sp_8(q) \le F_4(q)$, $q$ even	Wilson §4.9
$F_4(q) \le E_6(q),{}^2E_6(q),E_7(q),E_8(q)$	Brachter–Kaja [2], Lemma 2.3 (Dynkin sub-diagrams)

Standard facts used

• Facts D (Dickson). For $G=\operatorname{PSL}_2(q)$: a Sylow $p$-subgroup is elementary abelian of order $q$ and self-centralizing on its non-identity elements; every $p'$-element lies in a cyclic torus of order $(q\pm1)/\gcd(2,q-1)$ which is the centralizer of each of its elements of order $>2$; for $q$ odd the centralizer of an involution is dihedral of order $q-\varepsilon$, $q\equiv\varepsilon\pmod4$. Sources: Dickson [6]; Huppert [10 Kap. II, §8] (Hauptsatz 8.27); Wilson [21 §3.3].

• Facts S (Suzuki). For $G=\operatorname{Sz}(q)$, $q=2^{2n+1}\geq8$: a Sylow $2$-subgroup $P$ has order $q^2$, $Z(P)=\Omega_1(P)$ is elementary abelian of order $q$ and contains every involution, all elements of $P\setminus Z(P)$ have order $4$ with square in $Z(P)$; $C(z)=P$ for each involution $z$ and $C(w)=\langle w\rangle Z(P)$ for $|w|=4$; elements of odd order have cyclic centralizers (the

orders $q - 1$, $q \pm\sqrt{2q + 1}$), which intersect pairwise trivially. Sources: Suzuki [18, 19]; Huppert–Blackburn [11 Chap. XI, §3]; Wilson [21 §4.2].

• Facts W (Ward). In ${}^{2}G_{2}(q)$, $q = 3^{2n+1} \ge27$: $|C(x)| = q(q^{2} - 1)$ and $C(x) \cong C_{2} \times\operatorname{PSL}_{2}(q)$ for an involution $x$; elements of order $3$ have centralizers of order $q^{3}$ or $2q^{2}$ (when they commute with an involution). Sources: Ward [20]; Kleidman [12].

• ATLAS [5]: element orders of $\operatorname{PSL}_{3}(4)$ and $\operatorname{Alt}(7)$; isomorphisms $\operatorname{SL}_{4}(2) \cong\operatorname{Alt}(8)$, $\operatorname{Sp}_{4}(2) \cong\operatorname{Sym}(6)$, $\operatorname{PSU}_{4}(2) \cong\operatorname{PSp}_{4}(3)$, $G_{2}(2)' \cong\operatorname{PSU}_{3}(3)$, and the low-rank orthogonal isomorphisms (Wilson [21 §3.11]); maximal subgroup containments for sporadic groups; Mihăilescu’s theorem: $2^{f} + 1 = 3^{k}$ only for $f \in\{1, 3\}$.

Acknowledgments

The research of Pallabi Manna is supported by Anusandhan National Research Foundation (ANRF)-India under the National Postdoctoral Fellowship scheme (File No. PDF/2025/006751). The author would like to express sincere gratitude to Professor Andrea Lucchini for his valuable assistance in establishing Theorem 1.2 and for his careful review of the manuscript. The author also acknowledges the excellent research facilities provided by the Department of Mathematics, IIT Hyderabad, and the mentorship of Dr. Rajesh Kannan for his constant support and motivation.

Statements and Declarations

Competing Interests. The authors have no competing interests to declare that are relevant to the content of this article.

Data Availability

Data sharing is not applicable to this article, as no datasets were used or generated during this study.