Forbidden subgraphs of TI-power graphs of finite groups

Huani Li; Jin Chen; Shixun Lin

doi:10.1515/math-2024-0099

Article Open Access

Forbidden subgraphs of TI-power graphs of finite groups

Huani Li , Jin Chen and Shixun Lin

Published/Copyright: February 13, 2025

Published by

Become an author with De Gruyter Brill

Submit Manuscript Author Information Explore this Subject

$Open Mathematics$

From the journal Open Mathematics Volume 23 Issue 1

Abstract

Given a finite group $G$ with identity $e$ , the TI-power graph (trivial intersection power graph) defined on $G$ , denoted by $Γ ( G )$ , is an undirected graph with vertex set $G$ where distinct vertices $a$ and $b$ are adjacent if $⟨ a ⟩ ∩ ⟨ b ⟩ = { e }$ . We classify all finite groups whose TI-power graph is claw-free, $K 1 , 4$ -free, $C 4$ -free, and $P 4$ -free. In addition, we classify the finite groups whose TI-power graph is a threshold graph, a cograph, a chordal graph, and a split graph.

Keywords: TI-power graphs; forbidden subgraphs; finite groups

MSC 2010: 05C25

1 Introduction

Graph representations on some algebraic structures have been actively studied in the literature, because of some valuable applications (cf. [1,2]). Assume that $G$ is a group. In 2000, Kelarev and Quinn [3] introduced the power graph of a group, denoted by $P → ( G )$ , which is a directed graph with vertex set $G$ , and for distinct $x , y ∈ G$ , there is an arc from $x$ to $y$ if and only if $y$ is a power of $x$ . It is possible to consider the underlying graph of a power graph. In 2009, Chakrabarty et al. [4] introduced the undirected power graph of $G$ , denoted by $P ( G )$ , which is the underlying graph of $P → ( G )$ . Namely, $P ( G )$ has a vertex set $G$ , and between two distinct vertices have an edge if and only if one is a power of the other. Abawajy et al. [5] and Kumar et al. [6] published two surveys on power graphs that contain a large number of results on Hamiltonian, clique number, planarity, automorphism group, chromatic number, spectrum, independent number, connectivity, and so on.

Note that in $P ( G )$ , if vertex $a$ is adjacent to vertex $b$ , then $⟨ a ⟩ ∩ ⟨ b ⟩$ is either $⟨ a ⟩$ or $⟨ b ⟩$ . Motivated by the above fact, Bera [7] first introduced the intersection power graph of $G$ , denoted by $P I ( G )$ , which is an undirected graph with vertex set $G$ , where distinct vertices $x$ and $y$ are adjacent if and only if either one of $x , y$ is $e$ , or $⟨ x ⟩ ∩ ⟨ y ⟩ ≠ { e }$ . Clearly, that $P ( G )$ is a spanning subgraph of $P I ( G )$ . In [7], Bera studied some basic properties of $P I ( G )$ . In particular, if $G$ is cyclic, the automorphism group of $P I ( G )$ was characterized. Lv and Ma [8] characterized the finite groups $G$ such that $P I ( G )$ is equal to $P ( G )$ or other graphs defined on groups, such as, commuting graph and enhanced power graph. In [9], the authors classified all finite groups $G$ so that $P I ( G )$ is toroidal and projective-planar. Ma et al. [10] obtained necessary and sufficient conditions when $P I ( G ) − { e }$ admits a perfect code, where $e$ is the identity of $G$ and $P I ( G ) − { e }$ is the subgraph obtained by deleting $e$ from $P I ( G )$ . Recently, Ma and Fu [11] studied metric and strong metric dimension of intersection power graphs of finite groups.

Let $G$ be a finite group with identity $e$ . In this article, we consider the following graphs: the TI-power graph (trivial intersection power graph) defined on $G$ , denoted by $Γ ( G )$ , is an undirected graph with vertex set $G$ , in which distinct vertices $a$ and $b$ are adjacent if $⟨ a ⟩ ∩ ⟨ b ⟩ = { e }$ . From the definition of a TI-power graph, we see that if we only consider the set $G \ { e }$ , then the induced subgraph of $Γ ( G )$ by $G \ { e }$ is equal to the complement of the induced subgraph of $P I ( G )$ by $G \ { e }$ .

A number of important graph classes can be defined either structurally or in terms of forbidden subgraphs, such as cographs, chordal graphs, split graphs, and threshold graphs. In [12], Manna et al. studied forbidden subgraphs of power graphs and determined completely the finite groups whose power graphs are threshold and split.

In 2022, Cameron [13] surveyed various graphs defined on a group, that is, this graph’s vertex set is consisting of group elements, and this graph’s edge set can reflect group structure using some way, such as, the power graph and the enhanced power graph, where the enhanced power graph of a group $G$ is a simple graph with vertex set $G$ , in which two distinct vertices $x , y$ are joined by an edge if $⟨ x , y ⟩$ is cyclic. Also, in [13], Cameron raised a question as follows: Classify all finite groups whose enhanced power graph is a chordal graph, a cograph,a threshold graph, and a split graph. Recently, Ma et al. [14] partly gave solutions for the aforementioned question.

Motivated by Cameron’s question, in this article, we characterize all finite groups whose TI-power graph is claw-free, $K 1 , 4$ -free, $C 4$ -free, and $P 4$ -free. As applications, we classify the finite groups whose TI-power graph is a threshold graph, a cograph, a chordal graph, and a split graph.

2 Preliminaries

We first introduce some definitions and notation, which will be used frequently in this article.

Every graph of this article is assumed to be a simple graph, namely, an undirected graph which has no loops and multiple edges. Given a graph, say $Γ$ , we always use $V ( Γ )$ and $E ( Γ )$ to denote the vertex set and edge set of $Γ$ , respectively. A path having $n$ vertices is denoted by $P n$ , and a cycle with length $m$ ( $m ≥ 3$ ) is denoted by $C n$ . In general, we use $2 K 2$ to denote a matching containing two edges, which is a graph consisting of two independent edges. Given a fixed graph $Δ$ , a graph is said to be $Δ$ -free if it contains no induced subgraphs isomorphic to $Δ$ . In $Γ$ , if a subset $C ⊆ V ( Γ )$ induces a complete subgraph of $Γ$ , then $C$ is called a clique in $Γ$ . If a subset $D ⊆ V ( Γ )$ induces an empty subgraph of $Γ$ , then $C$ is called an independent set in $Γ$ . Let $a , b ∈ V ( Γ )$ be distinct. The independence number of $Γ$ , denoted by $β ( Γ )$ , is the cardinality of a maximum independent set of $Γ$ . If ${ a , b } ∈ E ( Γ )$ , then we denote this by $a ∼ Γ b$ , and we simply use $a ∼ b$ to denote it if this situation considered is unambiguous. In particularly, we denote a path containing $n$ vertices using simply $a 1 ∼ a 2 ∼ … ∼ a n$ , where ${ a i , a i + 1 } ∈ E ( Γ )$ with all $1 ≤ i ≤ n − 1$ . Also, we denote a cycle with length $n$ ( $n ≥ 3$ ) simply by $a 1 ∼ a 2 ∼ … ∼ a n ∼ a 1$ , where ${ a 1 , a n } ∈ E ( Γ )$ , and for any $1 ≤ i ≤ n − 1$ , ${ a i , a i + 1 } ∈ E ( Γ )$ .

Every group considered in our article is assume to be finite. In general, $G$ always denotes a finite group with identity element $e$ . Given an element $g$ of $G$ , $⟨ g ⟩$ denotes the cyclic subgroup of $G$ generated by $g$ , and $∣ ⟨ g ⟩ ∣$ is called the order of $g$ which is denoted by $o ( g )$ . If $o ( g ) = 2$ , then $g$ is called an involution. In general, $Z n$ denotes the cyclic group of order $n$ . We use $Z ( G )$ to denote the center of $G$ , that is, $Z ( G ) = { x ∈ G : x g = g x for any g ∈ G }$ . Note that $Z ( G )$ is a subgroup of $G$ . The spectrum of $G$ is the set of orders of all elements of $G$ and is denoted by $π e ( G )$ . Also, we use $π ( G )$ to denote the set of all prime divisors of the order of $G$ . As usual, the $k$ -fold direct product of $Z n$ is denoted by $Z n k$ .

Given an integer $n ≥ 3$ , this article uses $D 2 n$ to denote the dihedral group with $2 n$ elements. It is widely known that $D 2 n$ has a presentation as follows:

(1)

$D 2 n = ⟨ x , y : x n = y 2 = e , y x = x − 1 y ⟩ .$

Note that $D 2 n$ is non-abelian.

Given an integer $m ≥ 2$ , the dicyclic group with $4 m$ elements is denoted by $Q 4 m$ and possesses a presentation as follows:

(2)

$Q 4 m = ⟨ x , y : x m = y 2 , x 2 m = y 4 = e , x y = y x − 1 ⟩ .$

Note that a dicyclic group is also called a generalized quaternion group and $Q 4 m$ is an extension of $Z 2$ by $Z 2 m$ . Also, $Q 4 m$ is non-abelian. Clearly, one can verify that $Q 4 m$ has a unique involution, which is $y 2$ .

In this article, we use $Φ$ to denote the set of finite groups $G$ satisfying the following:

$G$ is a two-group;
$G$ has at least three involutions;
if $G$ has distinct cyclic subgroups $⟨ a ⟩ , ⟨ b ⟩$ of order 4, then $∣ ⟨ a ⟩ ∩ ⟨ b ⟩ ∣ = 2$ .

In particular, we call a group

$G$ is a

$Φ$ -group if

$G ∈ Φ$ .

Observation 2.1

Suppose that $G$ is an abelian group. Then $G$ is a $Φ$ -group if and only if $G ≅ Z 2 k × Z 2 t$ for some $k ≥ 1 , t ≥ 1$ .

There exist non-abelians $G$ such that $G$ is a $Φ$ -group. For example, for every integer $t ≥ 2$ , the dihedral group $D 2 × 2 t$ is a $Φ$ -group. Certainly, besides dihedral groups, there exists a non-abelian group which is a $Φ$ -group. For example, the Modular group $M 16$ of order 16 has a presentation as follows:

$M 16 = ⟨ y , x : y 8 = x 2 = e , x y x = y 5 ⟩ .$

It is easy to see that $M 16 = ⟨ y ⟩ ∪ { y x , y 2 x , … , y 7 x , x }$ . Also, $M 16$ has only three involutions that are $x , y 4 , y 4 x$ , and $o ( y x ) = o ( y 3 x ) = o ( y 5 x ) = o ( y 7 x ) = 8$ . It follows that $M 16$ has precisely two cyclic subgroups of order 4, that is, $⟨ y 2 ⟩$ and $⟨ y 2 x ⟩$ . Since $⟨ y 2 ⟩ ∩ ⟨ y 2 x ⟩ = { e , y 4 }$ , we have that $M 16$ is a $Φ$ -group.

3 Claw-free and $K 1 , 4$ -free TI-power graphs

In this section, we characterize all finite groups whose TI-power graph is claw-free (Theorem 3.5) and $K 1 , 4$ -free (Theorem 3.6).

Note that in $Γ ( G )$ , the identity element $e$ is always adjacent to every other vertex. Observe that the following results hold.

Observation 3.1

Given a positive integer $t$ at least 2, $Γ ( G )$ is $K 1 , t$ -free if and only if $β ( Γ ( G ) ) ≤ t − 1$ .

Observation 3.2

$Γ ( G )$ is complete, if and only if $β ( Γ ( G ) ) = 1$ , if and only if $G ≅ Z 2 t$ with $t ≥ 1$ .

From the aforementioned two observations, it follows that $Γ ( G )$ is $K 1 , 2$ -free if and only if $G ≅ Z 2 t$ with $t ≥ 1$ . In the following, we determine all finite groups whose TI-power graph is claw-free (or $K 1 , 3$ -free).

Lemma 3.3

If $π e ( G ) ⊆ { 1 , 2 , 3 }$ , then $Γ ( G )$ is claw-free.

Proof

Note that every involution is adjacent to every other vertex in $Γ ( G )$ . It follows that $β ( Γ ( G ) ) ≤ 2$ . Thus, by Observation 3.1, $Γ ( G )$ is claw-free.□

Lemma 3.4

If $Γ ( G )$ is claw-free, then $π e ( G ) ⊆ { 1 , 2 , 3 }$ .

Proof

Suppose that there exists a prime $p$ such that $p ∣ ∣ G ∣$ and $p ≥ 5$ . Then $G$ has a subgroup $⟨ g ⟩$ of order $p$ . Taking three distinct generators of $⟨ g ⟩$ , the three generators will form an independent set of $Γ ( G )$ . It follows that $β ( Γ ( G ) ) ≥ 3$ , a contradiction by Observation 3.1. We conclude that $π ( G ) ⊆ { 2 , 3 }$ . If $G$ has an element $a$ of order 4, then ${ a , a − 1 , a 2 }$ is an independent set of $Γ ( G )$ , and so $β ( Γ ( G ) ) ≥ 3$ , a contradiction. Thus, $G$ has no element of order 4. Similarly, we also can see that $G$ has no element of order 9 or 6. It follows that $π e ( G ) ⊆ { 1 , 2 , 3 }$ .□

Theorem 3.5

$Γ ( G )$ is claw-free if and only if $π e ( G ) ⊆ { 1 , 2 , 3 }$ , if and only if G is isomorphic to one of the following:

$Z 2 m$ for some $m ≥ 2$ ;
A nilpotent group of class at most 3; In particular, the group has exponent 3;
$N ⋊ K$ is a Frobenius group, where either $N ≅ Z 3 t , K ≅ Z 2$ or $N ≅ Z 2 2 t , K ≅ Z 3$ , where $t ≥ 1$ .

Proof

The required result follows from the main results of [15, 16] and Lemmas 3.3 and 3.4.□

Theorem 3.6

$Γ ( G )$ is $K 1 , 4$ -free if and only if, $π e ( G ) ⊆ { 1 , 2 , 3 , 4 }$ and if G has two distinct cyclic subgroups $⟨ a ⟩ , ⟨ b ⟩$ of order 4, then $∣ ⟨ a ⟩ ∩ ⟨ b ⟩ ∣ = 1$ .

Proof

We first suppose that $Γ ( G )$ is $K 1 , 4$ -free. By Observation 3.1, we see that $β ( Γ ( G ) ) ≤ 3$ . Suppose that $G$ has an element $a$ of order at least 5. Then consider the generators of $⟨ a ⟩$ , we have $β ( Γ ( G ) ) ≥ φ ( o ( a ) )$ , where $φ$ is the Euler’s totient function. Clearly, if $o ( a ) ≠ 6$ , then $β ( Γ ( G ) ) ≥ 4$ , a contradiction. If $o ( a ) = 6$ , then ${ a , a 2 , a 4 , a 5 }$ is an independent set of $Γ ( G )$ , and so $β ( Γ ( G ) ) ≥ 4$ , which is impossible. It follows that $π e ( G ) ⊆ { 1 , 2 , 3 , 4 }$ . Moreover, if $G$ has two distinct cyclic subgroups $⟨ a ⟩ , ⟨ b ⟩$ of order 4 with $∣ ⟨ a ⟩ ∩ ⟨ b ⟩ ∣ = 2$ , then ${ a , a 3 , b , b 3 }$ is an independent set of $Γ ( G )$ , which implies that $β ( Γ ( G ) ) ≥ 4$ , a contradiction. Thus, if $G$ has two distinct cyclic subgroups, then their intersection is trivial, as desired.

For the converse, suppose that $π e ( G ) ⊆ { 1 , 2 , 3 , 4 }$ and if $G$ has two distinct cyclic subgroups $⟨ a ⟩ , ⟨ b ⟩$ of order 4, then $∣ ⟨ a ⟩ ∩ ⟨ b ⟩ ∣ = 1$ . It is easy to see that $β ( Γ ( G ) ) ≤ 3$ , and so Observation 3.1 implies the required result.□

Remark 3.7

There exist such groups $G$ such that $π e ( G ) = { 1 , 2 , 3 , 4 }$ , and every two distinct cyclic subgroups of order 4 have trivial intersection. For example, for the symmetric group on four objects $S 4$ , we have that $π e ( S 4 ) = { 1 , 2 , 3 , 4 }$ , $S 4$ has three pairwise distinct cyclic subgroups of order 4, and every two distinct cyclic subgroups of order 4 have trivial intersection.

Let $Z 3 2 ⋊ Z 4 ≅ ⟨ a , b , c : a 3 = b 3 = c 4 = e , a b = b a = c b c 3 , a 2 b = c a c 3 ⟩$ , which is the semidirect product of $Z 3 2$ and $Z 4$ acting faithfully. In fact, $Z 3 2 ⋊ Z 4$ is the ninth group of order 36 in the SmallGroups library of GAP. The subgroup lattice of $Z 3 2 ⋊ Z 4$ is displayed in Figure 1, where $S 3$ is the symmetric group on three letters. One can easily see that $π e ( Z 3 2 ⋊ Z 4 ) = { 1 , 2 , 3 , 4 }$ , and if $Z 3 2 ⋊ Z 4$ has two distinct cyclic subgroups $⟨ a ⟩ , ⟨ b ⟩$ of order 4, then $∣ ⟨ a ⟩ ∩ ⟨ b ⟩ ∣ = 1$ . Actually, $Z 3 2 ⋊ Z 4$ has nine cyclic subgroups of order 4 and 9 involutions, and every involution precisely belongs to one cyclic subgroup of order 4.

$Figure 1 Subgroup lattice of Z 3 2 ⋊ Z 4 {{\mathbb{Z}}}_{3}^{2}\hspace{0.33em}\rtimes \hspace{0.33em}{{\mathbb{Z}}}_{4} .$

Figure 1

Subgroup lattice of $Z 3 2 ⋊ Z 4$ .

4 $C 4$ -free TI-power graphs

This section will characterize all finite group whose TI-power graph is $C 4$ -free (Theorem 4.3). As an application, we classify all finite nilpotent groups whose TI-power graph is $C 4$ -free (Corollary 4.4).

First, we recall the following elementary result.

Lemma 4.1

[17, Theorem 5.4.10 (ii)] For a prime p, a p-group having a unique subgroup of order p is either cyclic or generalized quaternion.

Lemma 4.2

Suppose that $Γ ( G )$ is $C 4$ -free. Then the following hold:

if there exist distinct primes p and q in $π ( G )$ , then one of them must be 2;
if there exists an odd prime $q ∈ π ( G )$ , then G has a unique cyclic subgroup of order q;
if G is not a p-group, then $2 ∈ π e ( G )$ and $4 ∉ π e ( G )$ .

Proof

Suppose that there exist two distinct odd primes $p , q ∈ π ( G )$ . Let $a , b ∈ G$ with $o ( a ) = p$ and $o ( b ) = q$ . Then the subgraph induced by ${ a , b , a − 1 , b − 1 }$ is isomorphic to $C 4$ , a contradiction. Thus, (i) holds. Suppose that there exists an odd prime $q ∈ π ( G )$ . If $G$ has two distinct cyclic subgroups of order $q$ , say $⟨ x ⟩$ and $⟨ y ⟩$ , then the subgraph induced by ${ x , y , x − 1 , y − 1 }$ is isomorphic to $C 4$ , a contradiction. Thus, (ii) is valid.

Finally, suppose that $G$ is not a $p$ -group. Then by (i), we see that $2 ∈ π ( G )$ , and so $2 ∈ π e ( G )$ . As a result, there exists an odd prime $q ∈ π ( G )$ . Let $z ∈ G$ with $o ( z ) = q$ . If $G$ has an element $w$ of order 4, then it is clear that the subgraph induced by ${ z , w , z − 1 , w − 1 }$ is isomorphic to $C 4$ , a contradiction. Thus, (iii) is valid.□

Theorem 4.3

$Γ ( G )$ is $C 4$ -free if and only if G is isomorphic to one of the following:

$Z p m$ for some prime p and positive integer $m ≥ 1$ ;
$Q 4 × 2 t$ for some positive integer $t ≥ 1$ ;
$G$ is a 2-group and has at least three involutions; if G has distinct cyclic subgroups $⟨ a ⟩ , ⟨ b ⟩$ of order 4, then $∣ ⟨ a ⟩ ∩ ⟨ b ⟩ ∣ = 2$ ;
for some odd prime q, positive integers m and non-negative integer n,
(3) ${ 1 , 2 , q } ⊆ π e ( G ) ⊆ { 1 , 2 , q , q 2 , … , q m , 2 q , 2 q 2 , … , 2 q n }$
and G has a unique subgroup of order q.

Proof

We first prove the sufficiency. If $G$ is isomorphic to one of (i) and (ii), then clearly, $Γ ( G ) ≅ K 1 , ∣ G ∣ − 1$ , and so $Γ ( G )$ is $C 4$ -free.

Suppose next that $G$ is isomorphic to one of (iii). Assume, to the contrary, that $Γ ( G )$ has a subgraph induced by ${ a , b , c , d }$ isomorphic to $C 4$ , where $a ∼ b ∼ c ∼ d ∼ a$ . Clearly, every of ${ a , b , c , d }$ must not be $e$ . Suppose that one of ${ a , b , c , d }$ is an involution, say $a$ . Then there exists a cyclic subgroup $⟨ c ′ ⟩$ of order 4 in $⟨ c ⟩$ . If $b$ is an involution, then there exists a cyclic subgroup $⟨ d ′ ⟩$ of order 4 in $⟨ d ⟩$ , and so $∣ ⟨ d ′ ⟩ ∩ ⟨ c ′ ⟩ ∣ ≥ 2$ , a contradiction since $c$ and $d$ are adjacent in $Γ ( G )$ . It follows that $b$ is not an involution. Let $⟨ b ′ ⟩$ be a cyclic subgroup of order 4 in $⟨ b ⟩$ . Then $∣ ⟨ b ′ ⟩ ∩ ⟨ c ′ ⟩ ∣ ≥ 2$ , a contradiction. We conclude that every of ${ a , b , c , d }$ is not an involution. Let $⟨ a ′ ⟩ , ⟨ b ′ ⟩$ be two cyclic subgroups of order 4 in $⟨ a ⟩$ and $⟨ b ⟩$ , respectively. Then $∣ ⟨ a ′ ⟩ ∩ ⟨ b ′ ⟩ ∣ ≥ 2$ , and hence, $a$ and $b$ are non-adjacent in $Γ ( G )$ , a contradiction.

Finally, assume that $G$ is one of (iv). Suppose for a contradiction that $Γ ( G )$ has an induced subgraph by ${ a , b , c , d }$ isomorphic to $C 4$ , where $a ∼ b ∼ c ∼ d ∼ a$ . Since $G$ has a unique subgroup of order $q$ , it follows that one of $a , b$ must be an involution. Without loss of generality, assume that $a$ is an involution. Therefore, $q ∣ o ( b )$ . Similarly, we have that $c$ must be an involution. However, in this case, $a$ is adjacent to $c$ in $Γ ( G )$ , which is impossible.

We then prove the necessity. Suppose that $Γ ( G )$ is $C 4$ -free. By Lemma 4.2 (i), we have $π ( G ) ⊆ { 2 , q }$ , where $q$ is an odd prime. We consider the following three cases.

Case 1. $π ( G ) = { 2 }$ .

If $G$ has a unique involution, then by Lemma 4.1, $G$ is one group of (i) or (ii). If $G$ has two distinct involutions, by Sylow theorems, $G$ has at least three involutions. Particularly, in this case, if $G$ has distinct cyclic subgroups $⟨ a ⟩ , ⟨ b ⟩$ of order 4, then $∣ ⟨ a ⟩ ∩ ⟨ b ⟩ ∣ = 2$ ; Otherwise, ${ a , b , a − 1 , b − 1 }$ would induce a $C 4$ . As a consequence, $G$ is one group of (iii).

Case 2. $π ( G ) = { q }$ .

By Lemma 4.2 (ii), in this case, $G$ has a unique subgroup of order $q$ . Now Lemma 4.1 implies that $G$ is isomorphic to one group in (i), as desired.

Case 3. $π ( G ) = { 2 , q }$ .

It follows from Lemma 4.2 (iii) that $4 ∉ π e ( G )$ , and so (3) holds. Also, Lemma 4.2 (ii) implies that $G$ has a unique cyclic subgroup of order $q$ . Thus, $G$ is isomorphic to one group in (iv), as desired.□

By applying Theorem 4.3 to nilpotent groups, we have the following result.

Corollary 4.4

Let G be a nilpotent group. Then $Γ ( G )$ is $C 4$ -free if and only if G is isomorphic to one of the following:

$Z p m$ for some prime p and positive integer $m ≥ 1$ ;
$Q 4 × 2 t$ for some positive integer $t ≥ 1$ ;
a $Φ$ -group;
$Z 2 k × Z q t$ , where q is an odd prime and $k , t ≥ 1$ .

Note that by Observation 2.1, if $G$ is an abelian $Φ$ -group, then $G$ has no subgroups isomorphic to $Z 4 × Z 4$ . Thus, applying Corollary 4.4 to abelian groups, we have the following result.

Corollary 4.5

Let G be an abelian group. Then $Γ ( G )$ is $C 4$ -free if and only if G is isomorphic to one of the following:

$Z p m$ for some prime p and positive integer $m ≥ 1$ ;
$Z 2 k × Z q t$ , where $q$ is a prime and $k , t ≥ 1$ .

5 $P 4$ -free TI-power graphs

In this section, we shall characterize all finite groups whose TI-power graph is $P 4$ -free (Theorem 5.4).

Observation 5.1

Let $n ≥ 3$ and $a , b ∈ Z n \ { e }$ with $a ≠ b$ . Then ${ a , b }$ is an edge of $Γ ( Z n )$ if and only if $( o ( a ) , o ( b ) ) = 1$ .

Lemma 5.2

Suppose that $Γ ( G )$ is $P 4$ -free. Then for any $g ∈ G$ , $∣ ⟨ g ⟩ ∣$ cannot have three pairwise distinct prime divisors.

Proof

Let $g ∈ G$ . Suppose, for a contradiction, that $p q r ∣ ∣ ⟨ g ⟩ ∣$ , where $p , q , r$ are pairwise distinct primes. Then there exists an element $a ∈ ⟨ g ⟩$ such that $o ( a ) = p q r$ . By Observation 5.1, it is easy to see that, the subset ${ a p , a q r , a p r , a q }$ would induce a subgraph isomorphic to $P 4$ , where $a p ∼ a q r ∼ a p r ∼ a q$ , which is impossible.□

Lemma 5.3

Suppose that ${ a , b , c , d } ⊆ V ( Γ ( G ) )$ induces a subgraph isomorphic to $P 4$ , where $a ∼ b ∼ c ∼ d$ . Then $∣ π ( ⟨ a ⟩ ) ∣ ≥ 2$ and $∣ π ( ⟨ d ⟩ ) ∣ ≥ 2$ .

Proof

Note that $e ∉ { a , b , c , d }$ . We first prove $∣ π ( ⟨ a ⟩ ) ∣ ≥ 2$ . Assume, to the contrary, that $o ( a ) = p m$ for some prime $p$ and positive integer $m$ . Let $x ∈ ⟨ a ⟩$ with $o ( x ) = p$ . Then we deduce that both $∣ ⟨ a ⟩ ∩ ⟨ d ⟩ ∣$ and $∣ ⟨ a ⟩ ∩ ⟨ c ⟩ ∣$ are powers of $p$ . It follows that $x ∈ ⟨ a ⟩ ∩ ⟨ c ⟩ ∩ ⟨ d ⟩$ , which implies that $c$ and $d$ are non-adjacent in $Γ ( G )$ , a contradiction. Similarly, we also can prove $∣ π ( ⟨ d ⟩ ) ∣ ≥ 2$ .□

In the following, we provide a characterization for the groups with $P 4$ -free TI-power graphs.

Theorem 5.4

$Γ ( G )$ is $P 4$ -free if and only if G satisfies the following two conditions:

for every $g ∈ G$ , $∣ π ( ⟨ g ⟩ ) ∣ ≤ 2$ ;
for distinct $x , y ∈ G$ , if $∣ π ( ⟨ x ⟩ ) ∣ = ∣ π ( ⟨ y ⟩ ) ∣ = 2$ , then either $⟨ x ⟩ ∩ ⟨ y ⟩ = { e }$ or $∣ π ( ⟨ x ⟩ ∩ ⟨ y ⟩ ) ∣ = 2$ .

Proof

We first prove the necessity. Suppose that $Γ ( G )$ is $P 4$ -free. Then (i) holds by Lemma 5.2. In the following, we shall prove that (ii) is valid. Assume that there exist two distinct $x , y ∈ G$ such that $∣ π ( ⟨ x ⟩ ) ∣ = ∣ π ( ⟨ y ⟩ ) ∣ = 2$ . By contradiction, it suffices to show that $∣ π ( ⟨ x ⟩ ∩ ⟨ y ⟩ ) ∣ = 1$ is impossible. Now let $∣ ⟨ x ⟩ ∩ ⟨ y ⟩ ∣ = p l$ for some prime $p$ and positive integer $l$ . Let

$o ( x ) = p m 1 q n 1 , o ( y ) = p m 2 r n 2 ,$

where $p , q , r$ are primes with $p ≠ q$ and $p ≠ r$ , and $m 1 , m 2 , n 1 , n 2$ are positive integers. Note that $q$ and $r$ may be equal. Furthermore, we may assume that

$⟨ x ⟩ = ⟨ x 1 ⟩ ⟨ x 2 ⟩ , ⟨ y ⟩ = ⟨ y 1 ⟩ ⟨ y 2 ⟩ ,$

where $⟨ x 1 ⟩$ and $⟨ x 2 ⟩$ are the Sylow $p$ -subgroup and the Sylow $q$ -subgroup of $⟨ x ⟩$ , respectively, and $⟨ y 1 ⟩$ and $⟨ y 2 ⟩$ are the Sylow $p$ -subgroup and the Sylow $r$ -subgroup of $⟨ y ⟩$ , respectively. Clearly, $⟨ x 2 ⟩ ∩ ⟨ y 2 ⟩ = { e }$ . It follows that $x , y 2 , x 2 , y$ are four pairwise distinct vertices of $Γ ( G )$ . If $⟨ x ⟩ ∩ ⟨ y 2 ⟩ ≠ { e }$ , then exists an element $z$ of order $r$ such that $z ∈ ⟨ x ⟩ ∩ ⟨ y 2 ⟩$ , and so $z ∈ ⟨ x 2 ⟩$ , which implies that $z ∈ ⟨ x 2 ⟩ ∩ ⟨ y 2 ⟩$ , a contradiction. Thus, we have $⟨ x ⟩ ∩ ⟨ y 2 ⟩ = { e }$ . Similarly, we also have $⟨ y ⟩ ∩ ⟨ x 2 ⟩ = { e }$ . It follows that ${ x , y 2 , x 2 , y }$ induces a subgraph isomorphic to $P 4$ , where $x ∼ y 2 ∼ x 2 ∼ y$ , a contradiction. Thus, (ii) holds.

We next prove the sufficiency. Assume that both (i) and (ii) hold. By contradiction, suppose that $Γ ( G )$ has a subgraph induced by ${ x , y , z , w }$ isomorphic to $P 4$ , where $x ∼ y ∼ z ∼ w$ . In view of Lemma 5.3, we have that $∣ π ( ⟨ x ⟩ ) ∣ ≥ 2$ and $∣ π ( ⟨ w ⟩ ) ∣ ≥ 2$ . Now (i) implies that $∣ π ( ⟨ x ⟩ ) ∣ = ∣ π ( ⟨ w ⟩ ) ∣ = 2$ . Thus, by (ii), we have that either $⟨ x ⟩ ∩ ⟨ w ⟩ = { e }$ or $∣ π ( ⟨ x ⟩ ∩ ⟨ w ⟩ ) ∣ = 2$ . If $⟨ x ⟩ ∩ ⟨ w ⟩ = { e }$ , then $x$ and $w$ are adjacent in $Γ ( G )$ , which is impossible. We conclude that $∣ π ( ⟨ x ⟩ ∩ ⟨ w ⟩ ) ∣ = 2$ . Now let

$π ( ⟨ x ⟩ ) = π ( ⟨ w ⟩ ) = { p , q } ,$

where $p , q$ are distinct primes. Let $a , b ∈ ⟨ x ⟩$ with $o ( a ) = p$ and $o ( b ) = q$ . Then $a , b ∈ ⟨ x ⟩ ∩ ⟨ w ⟩$ . Note that ${ x , z } ∉ E ( Γ ( G ) )$ . It follows that $⟨ x ⟩ ∩ ⟨ z ⟩ ≠ { e }$ , which implies that either $a ∈ ⟨ z ⟩$ or $b ∈ ⟨ z ⟩$ . Since $a , b ∈ ⟨ w ⟩$ , we see that $⟨ w ⟩ ∩ ⟨ z ⟩ ≠ { e }$ , this contradicts that $w$ and $z$ are adjacent in $Γ ( G )$ .□

If any element of $G$ is of prime power order, then $G$ is said to be a CP-group (cf. [18]). For example, $S 4$ is a CP-group. Moreover, for prime $p$ , every $p$ -group is also a CP-group. Thus, as a corollary of Theorem 5.4, the following holds.

Corollary 5.5

If G is a CP-group, then $Γ ( G )$ is $P 4$ -free.

6 Applications

6.1 Threshold graphs

A threshold graph is a graph containing no induced subgraph isomorphic to $P 4$ , $C 4$ or $2 K 2$ . Threshold graphs form the smallest family of graphs containing the one-vertex graph and closed under the operations of adding an isolated vertex and adding a vertex joined to all others. Threshold graphs can be applied in computer science and psychology [19,20].

In this section, we will classify all finite groups whose TI-power graph is threshold. The main result is stated below.

Theorem 6.1

$Γ ( G )$ is a threshold graph if and only if G is isomorphic to one of the following:

$Z p m$ for some prime p and positive integer $m ≥ 1$ ;
$Q 4 × 2 t$ for some positive integer $t ≥ 1$ ;
a $Φ$ -group;
$Z 2 q l$ for some odd prime q and positive integer $l$ ;
$D 2 q l$ for some odd prime q and positive integer $l$ ;
$D 2 ⋅ 2 q l$ for some odd prime q and positive integer $l$ .

We next provide a few lemmas before proving Theorem 6.1.

Lemma 6.2

If $Γ ( G )$ has a subgraph induced by ${ a , b , c , d }$ isomorphic to $2 K 2$ , where $a ∼ b$ and $c ∼ d$ , then the order of any of ${ a , b , c , d }$ is not a prime power. In particular, for a p-group G, $Γ ( G )$ is $2 K 2$ -free.

Proof

Suppose, without loss of generality, for a contradiction that $o ( a ) = p k$ for some prime $p$ and positive integer $k$ . Take $x ∈ ⟨ a ⟩$ with $o ( x ) = p$ . Since $⟨ a ⟩ ∩ ⟨ c ⟩ ≠ { e }$ and $⟨ a ⟩ ∩ ⟨ d ⟩ ≠ { e }$ , we have that both $∣ ⟨ a ⟩ ∩ ⟨ c ⟩ ∣$ and $∣ ⟨ a ⟩ ∩ ⟨ d ⟩ ∣$ are powers of $p$ . It follows that $x ∈ ⟨ a ⟩ ∩ ⟨ c ⟩$ , and so $x ∈ ⟨ c ⟩$ . Similarly, we also can deduce $x ∈ ⟨ d ⟩$ . Thus, $⟨ c ⟩ ∩ ⟨ d ⟩ ≠ { e }$ , which contradicts ${ c , d } ∈ E ( Γ ( G ) )$ .□

Lemma 6.3

If $Γ ( G )$ is $C 4$ -free, then $Γ ( G )$ is $2 K 2$ -free.

Proof

By Theorem 4.3 and Lemma 6.2, it suffices to show that if $G$ has a unique subgroup of order $q$ and

(4)

${ 1 , 2 , q } ⊆ π e ( G ) ⊆ { 1 , 2 , q , q 2 , … , q m , 2 q , 2 q 2 , … , 2 q n } ,$

where $q$ is an odd prime and $m , n$ are two positive integers, then $Γ ( G )$ is $2 K 2$ -free. Now suppose that $G$ has a unique subgroup of order $q$ and (4) holds, where $q$ is an odd prime. Suppose, for a contradiction, that $Γ ( G )$ has a subgraph induced by ${ a , b , c , d }$ isomorphic to $2 K 2$ , where $a ∼ b$ and $c ∼ d$ . Then it follows from Lemma 6.2 that neither $o ( a )$ nor $o ( b )$ is a prime power. Now (4) implies that $o ( a ) = 2 q t$ and $o ( b ) = 2 q k$ , where $t , k$ are two positive integers. Since $G$ has a unique subgroup of order $q$ , we infer that $⟨ a ⟩ ∩ ⟨ b ⟩$ must contain the unique subgroup of order $q$ . Therefore, $⟨ a ⟩ ∩ ⟨ b ⟩ ≠ { e }$ , contrary to $a ∼ b$ .□

Lemma 6.4

Suppose that G has a unique subgroup $⟨ a ⟩$ of order q, $C G ( a )$ has at most one involution and

(5)

${ 1 , 2 , q } ⊆ π e ( G ) ⊆ { 1 , 2 , q , q 2 , … , q m , 2 q , 2 q 2 , … , 2 q n } ,$

where q is an odd prime, m is a positive integer, and n is a non-negative integer. Then G is isomorphic to one of the following:

$Z 2 q l , D 2 q l , D 2 ⋅ 2 q l ,$

where l is a positive integer.

Proof

Let $∣ G ∣ = 2 k q l$ , where $k , l$ are positive integers. Let $Q$ be a Sylow $q$ -subgroups of $G$ . Note that $G$ has a unique subgroup of order $q$ . Then by Lemma 4.1, we have that $Q$ is cyclic. Since $a ∈ Q$ , one has $Q ⊆ C G ( a )$ . Let $Q = ⟨ y ⟩$ . Then we consider two cases as follows.

Case 1. $C G ( a )$ has no involutions.

In this case, by (5), we have that $π e ( G ) ⊆ { 1 , 2 , q , q 2 , … , q m } ,$ where $m$ is a positive integer. Note that $∣ Q ∣ = q l$ and $C G ( a )$ is a subgroup of $G$ . Suppose that $G$ has two distinct Sylow $q$ -subgroups. Then $∣ C G ( a ) ∣ > q l$ , which implies that 2 must divide $∣ C G ( a ) ∣$ . It follows that $C G ( a )$ has an involution, a contradiction. As a result, $Q$ is the unique Sylow $q$ -subgroup of $G$ . This also forces that $Q$ is normal in $G$ .

Next, let $P$ be a Sylow 2-subgroup of $G$ . Since $G$ has no elements of order 4, one has $P ≅ Z 2 k$ . In the following we prove $k = 1$ . Suppose, for a contradiction, that $k ≥ 2$ . Choosing distinct $x , z ∈ P \ { e }$ , we have that $x y , z y ∉ Q$ . It follows that both $x y$ and $z y$ are involutions. Thus,

$x y x = y − 1 , z y z = y − 1 .$

Note that $x z$ is also an involution. We deduce that

$( x z ) y ( x z ) = x ( z y z ) x = x y − 1 x = y .$

Consequently, $x z$ and $y$ commute, and so $o ( x z y ) = 2 q l$ , a contradiction. Hence, $n = 1$ . Now we may assume that $P = ⟨ x ⟩$ , where $x$ is an involution. It follows that $G = ⟨ x , y : x 2 = y q l = e , x y x = y − 1 ⟩ ≅ D 2 q l$ , as desired.

Case 2. $C G ( a )$ has only one involution, say $x$ .

Note that $∣ C G ( a ) ∣$ divides $2 k q l$ , and $G$ has only one cyclic subgroup $⟨ a ⟩ × ⟨ x ⟩$ of order $2 q$ . We must have that $∣ C G ( a ) ∣ = 2 q l$ . Next, we show that $G$ has a unique Sylow $q$ -subgroup. Otherwise, by Sylow theorems, we may assume that $G$ has at least $q + 1$ Sylow $q$ -subgroups. Note that any Sylow $q$ -subgroup of $G$ is isomorphic to $Z q l$ and has $q l − q l − 1$ generators. Thus, $G$ has at least $q l + 1 − q l − 1$ elements of order $q l$ . Note that any element of order $q l$ must belong to $C G ( a )$ . It follows that $q l + 1 − q l − 1 < 2 q l$ , this contradicts that $q$ is an odd prime. As a result, $G$ has a unique Sylow $q$ -subgroup $Q$ . Thus, $Q$ is a normal subgroup of $G$ .

Subcase 2.1. $k = 1$ .

In this case, $G = ⟨ x ⟩ Q = ⟨ x ⟩ ⟨ y ⟩$ . Note that both $x$ and $y$ can commute with $a$ . Thus, $a$ belongs to the center of $G$ . Since $C G ( a )$ has only one involution $x$ , we have that $G$ has only one involution $x$ . It follows that $⟨ x ⟩$ is also a normal subgroup of $G$ . This forces that $G = ⟨ x ⟩ × ⟨ y ⟩ ≅ Z 2 q l$ , as desired.

Subcase 2.2. $k ≥ 2$ .

Note that $⟨ y ⟩$ is a normal subgroup. Thus, $⟨ x ⟩ ⟨ y ⟩$ is a subgroup, and by a similar argument as in Subcase 2.1, we see that $⟨ x , y ⟩ ≅ Z 2 q l$ . Let $⟨ x ⟩ ⟨ y ⟩ = ⟨ x , y ⟩ = ⟨ h ⟩$ and let $P$ a Sylow 2-subgroup of $G$ with $x ∈ P$ . Clearly, $P$ is elementary abelian. It follows that $P$ has at least three involutions. Also, it is easy to see that for each $1 ≤ i ≤ l$ , $G$ has a unique cyclic subgroup of order $2 q i$ , and every cyclic subgroup of order $2 q i$ is contained in $⟨ h ⟩$ . Now choosing an involution $z ∈ P$ with $z ≠ x$ , we have that $z h ∉ ⟨ h ⟩$ . As a result, $z h$ is an involution. Thus, we have

$⟨ z , h : z 2 = h 2 q l = e , z h z = h − 1 ⟩ ≅ D 2 ⋅ 2 q l .$

Next, we prove that $G = ⟨ z , h ⟩$ . Suppose, for a contradiction, that there exists $w ∈ G \ ⟨ z , h ⟩$ . Then we must have $o ( w ) = 2$ and $∣ P ∣ ≥ 8$ . Without loss of generality, we may assume that $w ∈ P$ . Note that $w h$ is an involution. Thus, we have $w h w = h − 1$ . Note that $w$ and $z$ commute. W have that

$( w z ) h ( w z ) = z ( w h w ) z = z h − 1 z = h ,$

which implies that $( w z ) h = h ( w z )$ . It follows that $w z$ and $a$ commute, and therefore, we have $w z a$ has order $2 q$ . Note that $G$ has precisely one cyclic subgroup $⟨ x a ⟩$ of order $2 q$ . Consequently, $x = w z$ , namely, $w = x z ∈ ⟨ z , h ⟩$ , a contradiction. Thus, in this case, we have that $G = ⟨ z , h ⟩$ , as desired.□

We are ready to show Theorem 6.1.

Proof of Theorem 6.1

We first prove the sufficiency. By Theorem 4.3, we see that any group in (i)–(iii) is $C 4$ -free. Also, Corollary 5.5 and Lemma 6.2 imply that every $p$ -group is $P 4$ -free and $2 K 2$ -free, respectively. It follows that any group of (i)–(iii) is a threshold graph. Now let $G$ be a group of (iv)–(vi). Then $G$ has a unique subgroup $⟨ a ⟩$ of order $q$ , $C G ( a )$ has at most one involution and

(6)

${ 1 , 2 , q } ⊆ π e ( G ) ⊆ { 1 , 2 , q , q 2 , … , q l , 2 q , 2 q 2 , … , 2 q l } ,$

where $q$ is an odd prime, and $l$ is a positive integer. Clearly, Theorem 4.3 implies that $Γ ( G )$ is $C 4$ -free, and so $Γ ( G )$ is $2 K 2$ -free by Lemma 6.3. Now suppose that $∣ π ( ⟨ x ⟩ ) ∣ = ∣ π ( ⟨ y ⟩ ) ∣ = 2$ for distinct $x , y ∈ G$ . Then (6) implies that

$o ( x ) = 2 q t , o ( t ) = 2 q k , t , k ≥ 1 .$

Since $⟨ a ⟩$ is the unique subgroup of order $q$ in $G$ , we have that $⟨ a ⟩ ⊆ ⟨ x ⟩ ∩ ⟨ y ⟩$ . Let $u$ and $v$ be the involutions in $⟨ x ⟩$ and $⟨ y ⟩$ , respectively. Then $u , v ∈ C G ( a )$ . Also, since $C G ( a )$ has at most one involution, it follows that $u = v$ . This forces $u ∈ ⟨ x ⟩ ∩ ⟨ y ⟩$ . Therefore, we have $∣ π ( ⟨ x ⟩ ∩ ⟨ y ⟩ ) ∣ = 2$ . Now combining (6) and Theorem 5.4, we know that $Γ ( G )$ is $P 4$ -free, and so is a threshold graph.

We next prove the necessity. Suppose that $Γ ( G )$ is a threshold graph. Then $Γ ( G )$ is $C 4$ -free. By Theorem 4.3, we only need to show that $G$ is a group in (iv)–(vi). On the other hand, Theorem 4.3 also implies that $G$ has a unique subgroup $⟨ a ⟩$ of order $q$ ( $q$ is an odd prime) and (5) holds. Note that $Γ ( G )$ is $P 4$ -free. Suppose for a contradiction that $C G ( a )$ has two distinct involutions, say $u , v$ . Then $o ( u a ) = 2 q$ and $o ( v a ) = 2 q$ . It follows that $⟨ u a ⟩ ∩ ⟨ v a ⟩ = ⟨ a ⟩$ and so $∣ π ( ⟨ u a ⟩ ∩ ⟨ v a ⟩ ) ∣ = 1$ , and this is impossible as Theorem 5.4. We conclude that $C G ( a )$ has at most one involution. It follows from Lemma 6.4 that $G$ is a group in (iv)–(vi), as desired.□

6.2 Cographs

A graph is called a cograph provided that this graph contains no induced subgraph isomorphic to $P 4$ , that is, this graph is $P 4$ -free. The family of cographs is the smallest class of graphs containing the 1-vertex graph and is closed under the operations of disjoint union and complementation. Clearly, every threshold graph is also a cograph.

By Theorem 5.4, we have the following result.

Theorem 6.5

$Γ ( G )$ is a cograph if and only if G satisfies the following two conditions:

for every $g ∈ G$ , $∣ π ( ⟨ g ⟩ ) ∣ ≤ 2$ ;
for distinct $x , y ∈ G$ , if $∣ π ( ⟨ x ⟩ ) ∣ = ∣ π ( ⟨ y ⟩ ) ∣ = 2$ , then either $⟨ x ⟩ ∩ ⟨ y ⟩ = { e }$ or $∣ π ( ⟨ x ⟩ ∩ ⟨ y ⟩ ) ∣ = 2$ .

Apply Theorem 6.5 to nilpotent groups, by Lemma 4.1 and Theorem 6.5, the following holds.

Corollary 6.6

Let G be a nilpotent group. Then $Γ ( G )$ is a cograph if and only if G is isomorphic to one of the following:

a p-group, where p is a prime;
$Z p m q n$ , where p, q are distinct primes and $m , n ≥ 1$ ;
$Q 2 m × Z q n$ , where q is an odd prime, $m ≥ 3$ and $n ≥ 1$ .

6.3 Chordal graph

A graph is called a chordal graph if this graph has no induced cycles of length greater than 3. Namely, if a chordal graph has an induced subgraph isomorphic to cycle $C n$ , then $n = 3$ . Thus, if a chordal graph has a cycle of length at least 4, then the cycle must have a chord. It follows that if a graph is $P 4$ -free and $C 4$ -free, then this graph is a chordal graph. As a result, a threshold graph is also a chordal graph.

Theorem 6.7

$Γ ( G )$ is a chordal graph if and only if G is isomorphic to one of the following:

$Z p m$ for some prime p and positive integer $m ≥ 1$ ;
$Q 4 × 2 t$ for some positive integer $t ≥ 1$ ;
a $Φ$ -group;
a group G satisfying that for some odd prime q, positive integer m and non-negative integer n,
(7) ${ 1 , 2 , q } ⊆ π e ( G ) ⊆ { 1 , 2 , q , q 2 , … , q m , 2 q , 2 q 2 , … , 2 q n } ,$
and G has a unique subgroup of order q.

Proof

Suppose that $Γ ( G )$ is a chordal graph. Then $Γ ( G )$ is $C 4$ -free. In view of Theorem 4.3, we have that $G$ is a group of (i)–(iv), as desired.

Conversely, suppose that $G$ is a group of (i)–(iv). By Theorem 6.1, if $G$ is a group of (i)–(iii), then $Γ ( G )$ is a threshold graph, and so a chordal graph. Now let $G$ be a group in (iv), and let $a$ be an element of order $q$ . Then Theorem 4.3 implies that $Γ ( G )$ is $C 4$ -free. Suppose, for a contradiction, that $Γ ( G )$ has an induced subgraph $Δ$ isomorphic to $C n$ where $n ≥ 5$ . Then $Δ$ has an induced subgraph $Δ ′$ isomorphic to $P 4$ , say $a ∼ b ∼ c ∼ d$ , where ${ a , b } , { b , c } , { c , d } ∈ E ( Γ ( G ) )$ . Note that $Δ ′$ is also an induced subgraph of $Γ ( G )$ . It follows from Lemma 5.3 and (7) that $o ( a ) = 2 q l$ and $o ( d ) = 2 q t$ , where $l , t ≥ 1$ . This forces that $o ( b ) = 2$ , since $G$ has a unique subgroup $⟨ a ⟩$ of order $q$ . Now let $x$ be a vertex of $Δ$ with ${ x , a } ∈ E ( Γ ( G ) )$ . Since $⟨ x ⟩ ∩ ⟨ a ⟩ = { e }$ and $G$ has a unique subgroup $⟨ a ⟩$ of order $q$ , we have $q ∤ o ( x )$ . Thus, (7) implies $o ( x ) = 2$ . It follows that $x$ is adjacent to $b$ , a contradiction. We conclude that $Γ ( G )$ has no induced subgraph isomorphic to $C n$ , where $n ≥ 5$ . As a result, $Γ ( G )$ is a chordal graph.□

Corollary 6.8

$Γ ( G )$ is a chordal graph if and only if G is $C 4$ -free.

6.4 Split graphs

A graph is called split if its vertex set can be partitioned into the disjoint union of an independent set and a clique, here either of which may be empty, that is, both complete graph and null graph are split. Foldes and Hammer [21] showed that a graph is split if and only if this graph does not contain an induced subgraph isomorphic to one of these forbidden graphs: $C 4$ , $C 5$ and $2 K 2$ .

By Theorem 4.3, Corollary 6.8 and Lemma 6.3, the following result is valid.

Theorem 6.9

The following are equivalent for a group G:

$Γ ( G )$ is split;
$Γ ( G )$ is $C 4$ -free;
$Γ ( G )$ is chordal.

Acknowledgements

The authors are deeply grateful to the reviewers for their valuable comments that improved the manuscript.

Funding information: This work was supported by the Special Basic Cooperative Research Programs of Yunnan Provincial Undergraduate University’s Association (No. 202301BA070001-095) and Yunnan Provincial Reserve Talent Program for Young and Middle-aged Academic and Technical Leaders (No. 202405AC350086).
Author contributions: All authors have accepted responsibility for the entire content of this manuscript and consented to its submission to the journal, reviewed all the results, and approved the final version of the manuscript. All authors contributed equally in this work.
Conflict of interest: The authors state no conflicts of interest.
Data availability statement: No datasets were generated or analyzed during the current study.

References

[1] A. V. Kelarev, J. Ryan, and J. Yearwood, Cayley graphs as classifiers for data mining: The influence of asymmetries, Discrete Math. 309 (2009), no. 17, 5360–5369, DOI: https://doi.org/10.1016/j.disc.2008.11.030. 10.1016/j.disc.2008.11.030Search in Google Scholar

[2] M. Zhang, Software defined network energy efficient algorithm based on degree sequence of nodes, Microelectron. Comput. 38 (2021), no. 10, 65–72, DOI: https://doi.org/10.19304/J.ISSN1000-7180.2021.0059. Search in Google Scholar

[3] A. V. Kelarev and S. J. Quinn, A combinatorial property and power graphs of groups, Contrib. Gen. Algebr. 12 (2000), no. 2, 229–235.Search in Google Scholar

[4] I. Chakrabarty, S. Ghosh, and M. K. Sen, Undirected power graphs of semigroups, Semigroup Forum 78 (2009), 410–426, DOI: https://doi.org/10.1007/s00233-008-9132-y. 10.1007/s00233-008-9132-ySearch in Google Scholar

[5] J. Abawajy, A. Kelarev, and M. Chowdhury, Power graphs: A survey, Electron. J. Graph Theory Appl. 1 (2013), no. 2, 125–147, DOI: http://dx.doi.org/10.5614/ejgta.2013.1.2.6. 10.5614/ejgta.2013.1.2.6Search in Google Scholar

[6] A. Kumar, L. Selvaganesh, P. J. Cameron, and T. T. Chelvam, Recent developments on the power graph of finite groups - a survey, AKCE Int. J. Graphs Comb. 18 (2021), no. 2, 65–94, DOI: https://doi.org/10.1080/09728600.2021.1953359. 10.1080/09728600.2021.1953359Search in Google Scholar

[7] S. Bera, On the intersection power graph of a finite group, Electron. J. Graph Theory Appl. 6 (2018), no. 1, 178–189, DOI: http://dx.doi.org/10.5614/ejgta.2018.6.1.13. 10.5614/ejgta.2018.6.1.13Search in Google Scholar

[8] W. Lv and X. Ma, The intersection power graph associated with a finite group, ScienceAsia 47 (2021), 657–664, DOI: https://doi.org/10.2306/scienceasia1513-1874.2021.091. 10.2306/scienceasia1513-1874.2021.091Search in Google Scholar

[9] H. Li, X. Ma, and R. Fu, Finite groups whose intersection power graphs are toroidal and projective-planar, Open Math. 19 (2021), no. 1, 850–862, DOI: https://doi.org/10.1515/math-2021-0071. 10.1515/math-2021-0071Search in Google Scholar

[10] X. Ma, L. Li, and G. Zhong, Perfect codes in proper intersection power graphs of finite groups, Appl. Algebra Engrg. Comm. Comput. (2023), 1–13, DOI: https://doi.org/10.1007/s00200-023-00626-2. 10.1007/s00200-023-00626-2Search in Google Scholar

[11] X. Ma and R. Fu, Metric and strong metric dimension in intersection power graphs of finite groups, Comm. Algebra (2024), 1–12, DOI: https://doi.org/10.1080/00927872.2024.2423267. 10.1080/00927872.2024.2423267Search in Google Scholar

[12] P. Manna, P. J. Cameron, and R. Mehatari, Forbidden subgraphs of power graphs, Electron. J. Combin. 28 (2021), no. 3, P3.4, DOI: https://doi.org/10.37236/9961. 10.37236/9961Search in Google Scholar

[13] P. J. Cameron, Graphs defined on groups, Int. J. Group Theory 11 (2022), no. 2, 53–107, DOI: https://doi.org/10.22108/ijgt.2021.127679.1681. Search in Google Scholar

[14] X. Ma, S. Zahirović, Y. Lv, and Y. She, Forbidden subgraphs in enhanced power graphs of finite groups, Rev. R. Acad. Cienc. Exactas Fís. Nat. Ser. A Mat. RACSAM 118 (2024), 110, DOI: https://doi.org/10.1007/s13398-024-01611-1. 10.1007/s13398-024-01611-1Search in Google Scholar

[15] F. Levi and B. L. van der Waaerden, Uber eine besondere Klasse von gruppen, Abh. Math. Semin. Univ. Hambg. 9 (1933), 154–158, DOI: https://doi.org/10.1007/BF02940639. 10.1007/BF02940639Search in Google Scholar

[16] B. H. Neumann, Groups whose elements have bounded orders, J. Lond. Math. Soc. s1-12 (1937), no. 3, 195–198, DOI: https://doi.org/10.1112/jlms/s1-12.2.195. 10.1112/jlms/s1-12.2.195Search in Google Scholar

[17] D. Gorenstein, Finite Groups, Chelsea Publishing Company, New York, 1980. Search in Google Scholar

[18] A. L. Delgado and Y.-F. Wu, On locally finite groups in which every element has prime power order, Illinois J. Math. 46 (2002), no. 3, 885–891, DOI: https://doi.org/10.1215/ijm/1258130990. 10.1215/ijm/1258130990Search in Google Scholar

[19] V. Chvátal and P. L. Hammer, Aggregations of inequalities in integer programming, Ann. Discrete Math. 1 (1977), 145–162, DOI: https://doi.org/10.1016/S0167-5060(08)70731-3. 10.1016/S0167-5060(08)70731-3Search in Google Scholar

[20] P. B. Henderson and Y. Zalcstein, A graph-theoretic characterization of the PV class of synchronizing primitives, SIAM J. Sci. Comput. 6 (1977), no. 1, 88–108, DOI: https://doi.org/10.1137/0206008. 10.1137/0206008Search in Google Scholar

[21] S. Foldes and P. L. Hammer, Split graphs, Proceedings of the Eighth South-Eastern Conference on Combinatorics, Graph Theory and Computing, (Baton Rouge, La, 1977), Utilitas Mathematics, Winnipeg, pp. 311–315. Search in Google Scholar

Received: 2024-05-28

Revised: 2024-11-03

Accepted: 2024-11-08

Published Online: 2025-02-13

This work is licensed under the Creative Commons Attribution 4.0 International License.

Articles in the same Issue

https://doi.org/10.1515/math-2024-0099

Keywords for this article

TI-power graphs; forbidden subgraphs; finite groups

Creative Commons

BY 4.0

Forbidden subgraphs of TI-power graphs of finite groups

Article

Abstract

1 Introduction

2 Preliminaries

Observation 2.1

3 Claw-free and K1,4<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msub> <mml:mrow> <mml:mi>K</mml:mi> </mml:mrow> <mml:mrow> <mml:mn>1</mml:mn> <mml:mo>,</mml:mo> <mml:mn>4</mml:mn> </mml:mrow> </mml:msub> </mml:math> -free TI-power graphs

Observation 3.1

Observation 3.2

Lemma 3.3

Proof

Lemma 3.4

Proof

Theorem 3.5

Proof

Theorem 3.6

Proof

Remark 3.7

4 C 4 <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msub> <mml:mrow> <mml:mi>C</mml:mi> </mml:mrow> <mml:mrow> <mml:mn>4</mml:mn> </mml:mrow> </mml:msub> </mml:math> -free TI-power graphs

Lemma 4.1

Lemma 4.2

Proof

Theorem 4.3

Proof

Corollary 4.4

Corollary 4.5

5 P 4 <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msub> <mml:mrow> <mml:mi>P</mml:mi> </mml:mrow> <mml:mrow> <mml:mn>4</mml:mn> </mml:mrow> </mml:msub> </mml:math> -free TI-power graphs

Observation 5.1

Lemma 5.2

Proof

Lemma 5.3

Proof

Theorem 5.4

Proof

Corollary 5.5

6 Applications

6.1 Threshold graphs

Theorem 6.1

Lemma 6.2

Proof

Lemma 6.3

Proof

Lemma 6.4

Proof

Proof of Theorem 6.1

6.2 Cographs

Theorem 6.5

Corollary 6.6

6.3 Chordal graph

Theorem 6.7

Proof

Corollary 6.8

6.4 Split graphs

Theorem 6.9

Acknowledgements

References

Articles in the same Issue

Articles in the same Issue

Articles in the same Issue

3 Claw-free and $K 1 , 4$ -free TI-power graphs

4 $C 4$ -free TI-power graphs

5 $P 4$ -free TI-power graphs