On the Independence Number of the Prime-Coprime Graph of a Finite Group

Ravi Ranjan and Shubh Narayan Singh Surbhi Kumari and Shidra Jamil · 2026

Read On the Independence Number of the Prime-Coprime Graph of a Finite Group by Ravi Ranjan and Shubh Narayan Singh Surbhi Kumari and Shidra Jamil (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2604-18475.txt.

Introduction

Ranjan, Singh, Kumari, and Jamil study the prime-coprime graph of a finite group, joining elements whose orders share only 1 or a prime divisor. They characterize exactly which finite groups yield split graphs. A general lower bound covers the independence number for arbitrary finite groups. Explicit values follow for cyclic, dihedral, dicyclic, and semidihedral families, mapping independence across distinguished group types.

Catalog record

CREATORRavi Ranjan and Shubh Narayan Singh Surbhi Kumari and Shidra Jamil
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE34695
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2604.18475

Browse the full library · About the Tower of Babel

Full text

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

On the Independence Number of the Prime-Coprime Graph of a Finite Group Ravi Ranjan and Shubh Narayan Singh Surbhi Kumari and Shidra Jamil Abstract . The prime-coprime graph Θ ⁡ ( G ) \Theta(G) of a finite group G G is the simple graph with vertex set G G , where two distinct elements are adjacent whenever the greatest common divisor of their orders is either 1 1 or a prime. We characterize all finite groups G G for which Θ ⁡ ( G ) \Theta(G) is a split graph. We establish a general lower bound for the independence number of Θ ⁡ ( G ) \Theta(G) of an arbitrary finite group G G . Moreover, we explicitly compute the independence number of Θ ⁡ ( G ) \Theta(G) for several distinguished families of finite groups, including cyclic, dihedral, dicyclic, and semidihedral groups. 2020 Mathematics Subject Classification 05C25, 05C69 1. Introduction Graphs arising from finite groups have been extensively studied over the past two decades; see the survey in [ 3 ] . These graphs highlight the deep interplay between group theory and graph theory, allowing group-theoretic properties to be examined through graph invariants. Among recent constructions, the concept of prime–coprime graphs, introduced in 2021, has attracted considerable attention; see [ 1 , 8 , 11 , 14 , 15 , 16 , 17 , 18 ] . Let G be a finite group. The prime-coprime graph of G , denoted by \Theta(G) , is the simple graph with vertex set G , where two distinct vertices are adjacent whenever the greatest common divisor of their orders is either 1 or a prime [ 1 ] . This graph is also referred as the coprime order graph in the literature; see [ 8 , 11 ] . Adhikari and Banerjee [ 1 ] characterized the completeness and Eulerian properties of \Theta(G) , and determined its domination number, diameter, and girth. For specific groups G , they further studied Hamiltonicity, planarity, vertex connectivity, and the signless Laplacian spectrum of \Theta(G) . Hao et al. [ 8 ] classified finite groups G for which \Theta(G) is planar, and determined its vertex connectivity for finite cyclic, dihedral, and dicyclic groups. Li et al. proved that for any fixed integer k\geq 1 , there are only finitely many finite groups G such that \Theta(G) has (non)orientable genus k [ 11 ] . In [ 14 ] , the first two authors studied the Hamiltonicity and clique number of \Theta(G) for finite cyclic, dihedral, and dicyclic groups. The determination of the independence number of a graph is generally NP-hard. This graph invariant has been investigated for certain graphs associated with finite groups; see [ 4 , 7 , 10 , 12 , 13 ] . In this paper, we focus on the independence number of prime–coprime graphs of finite groups. The subsequent sections of this paper are organized as follows. Section 2 provides preliminary definitions and notation. In Section 3, we characterize all finite groups G for which \Theta(G) is a split graph. Furthermore, we establish a general lower bound for the independence number of \Theta(G) of an arbitrary finite group G . Moreover, we explicitly compute the independence number of \Theta(G) for the following four distinguished families of finite groups: \displaystyle\text{Cyclic groups }\,\,\Z_{n} \displaystyle=\langle a\,\colon a^{n}=1\rangle,\quad n\geq 1; \displaystyle\text{Dihedral groups }\,\,D_{2n} \displaystyle=\langle a,b\,\colon a^{n}=1,\,b^{2}=1,\,bab^{-1}=a^{-1}\rangle,\quad n\geq 3; \displaystyle\text{Dicyclic groups }\,\,Q_{4n} \displaystyle=\langle a,b\,\colon a^{2n}=1,\,b^{4}=1,\,bab^{-1}=a^{-1}\rangle,\quad n\geq 3; \displaystyle\text{Semidihedral groups }\,\,SD_{8n} \displaystyle=\langle a,b\,\colon a^{4n}=1,\,b^{2}=1,\,bab^{-1}=a^{2n-1}\rangle,\quad n\geq 3. 2. Preliminaries and Notation The cardinality of a set X is denoted by |X| . For sets A and B , their disjoint union is denoted by A\sqcup B , and the set difference is denoted by A\setminus B=\{x\in A\colon x\notin B\} . We denote by \N the set of all positive integers. For any integers a,b\in\N , we denote by (a,b) the greatest common divisor (gcd, for short) of a and b . The canonical prime factorization of an integer n>1 is a unique representation n=p_{1}^{k_{1}}\cdots p_{t}^{k_{t}} , where p_{1}<\cdots<p_{t} are primes and k_{1},\ldots,k_{t}\in\N . The number of distinct prime divisors of an integer n>1 is denoted by \omega(n) . A semiprime is a composite integer that is the product of two (possibly equal) primes. For every positive integer n , we denote by \varphi(n) Euler’s totient function of n . Unless stated otherwise, all groups considered are finite and nontrivial. Let G be a group. For every element g\in G , we denote by |g| the order of g , and by \langle g\rangle the cyclic subgroup generated by g . The order of G is denoted by |G| , and \pi(G) denotes the set of all prime divisors of |G| . We set P(G)=\bigl\{g\in G\ \colon|g|\in\pi(G)\cup\{1\}\bigr\} . The cyclic group of order n is denoted by \Z_{n} . Throughout the paper, all graphs are assumed to be simple. Let \Gamma be a graph. We denote by V(\Gamma) (resp. E(\Gamma) ) the set of all vertices (resp. edges) of \Gamma . For any two distinct vertices u,v\in V(\Gamma) , we denote by uv (or vu ) the edge of \Gamma with endpoints u and v . A dominating vertex of \Gamma is a vertex that is adjacent to every other vertex of \Gamma . For every positive integer m , we use the notation m\Gamma to denote the disjoint union of m copies of \Gamma . For any vertex-disjoint subgraphs \Gamma_{1} and \Gamma_{2} of \Gamma , we write \Gamma_{1}\sim\Gamma_{2} if every vertex of \Gamma_{1} is adjacent to every vertex of \Gamma_{2} in \Gamma . We denote by K_{n} the complete graph on n vertices, and by E_{n} the empty graph on n vertices. Let S be a nonempty subset of V(\Gamma) . The subgraph of \Gamma induced by S is denoted by \Gamma[S] , and \Gamma-S denotes the graph obtained by removing the vertices of S from \Gamma . The set S is called a clique (resp. independent set ) of \Gamma if \Gamma[S] is complete (resp. empty). An independent set of \Gamma is said to be maximal if it is inclusion-maximal, and maximum if it has the maximum cardinality among all independent sets of \Gamma . The independence number of \Gamma , denoted by \alpha(\Gamma) , is the cardinality of a maximum independent set of \Gamma . We write \Gamma_{1}\cong\Gamma_{2} whenever graphs \Gamma_{1} and \Gamma_{2} are isomorphic. A graph \Gamma is called a split graph if its vertex set V(\Gamma) admits a partition into two disjoint nonempty subsets K and I such that K forms a clique and I constitutes an independent set. The pair (C,I) is then referred to as a split partition of \Gamma . Moreover, if every vertex of K is adjacent to every vertex of I , then \Gamma is said to be a complete split graph . It was established in [ 5 ] that a graph is split if and only if it contains no induced subgraph isomorphic to C_{4} , C_{5} , or 2K_{2} . Let H be a graph with vertex set \{1,2,\dots,t\} , and let \mathcal{G}=\{\Gamma_{1},\Gamma_{2},\dots,\Gamma_{t}\} be a family of pairwise vertex‑disjoint graphs. The H ‑join of \mathcal{G} , denoted H[\mathcal{G}] , is the graph obtained by replacing each vertex

Read the complete text