arxiv: 2604.18475 · v1 · submitted 2026-04-20 · 🧮 math.GR

Recognition: unknown

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

Ravi Ranjan, Shidra Jamil, Shubh Narayan Singh, Surbhi Kumari

Pith reviewed 2026-05-10 03:29 UTC · model grok-4.3

classification 🧮 math.GR

keywords prime-coprime graphindependence numbersplit graphfinite groupscyclic groupsdihedral groupsdicyclic groupssemidihedral groups

0 comments

The pith

Finite groups G for which the prime-coprime graph Θ(G) is a split graph are completely characterized, with a general lower bound on the independence number and exact values for cyclic, dihedral, dicyclic and semidihedral groups.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper defines the prime-coprime graph Θ(G) whose vertices are the elements of a finite group G and whose edges join distinct elements whose orders have greatest common divisor equal to 1 or a prime number. It identifies precisely those groups G for which Θ(G) is a split graph, that is, whose vertices partition into a clique and an independent set. It also proves a lower bound that applies to the independence number of Θ(G) for every finite group and calculates the exact independence number when G belongs to the families of cyclic, dihedral, dicyclic or semidihedral groups. These results translate algebraic information about element orders into combinatorial statements about an associated graph.

Core claim

We characterize all finite groups G for which Θ(G) is a split graph. We establish a general lower bound for the independence number of Θ(G) of an arbitrary finite group G. Moreover, we explicitly compute the independence number of Θ(G) for several distinguished families of finite groups, including cyclic, dihedral, dicyclic, and semidihedral groups.

What carries the argument

The prime-coprime graph Θ(G) on the elements of G, with adjacency when the gcd of the orders is 1 or a prime.

If this is right

The independence number of Θ(G) is bounded from below for every finite group G, guaranteeing a minimum size for any largest set of elements whose pairwise order gcds are neither 1 nor prime.
Exact independence numbers are available for all cyclic groups, all dihedral groups, all dicyclic groups and all semidihedral groups.
Only the groups in the characterization have the property that the vertices of Θ(G) can be partitioned into a clique and an independent set with no edges between the parts.
The lower bound and explicit formulas together give concrete numerical information about the largest subsets of elements satisfying the order-gcd condition for the listed families.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The lower bound may become equality for some infinite families of groups, revealing a direct link between the distribution of element orders and the size of maximal independent sets in Θ(G).
The split-graph characterization could be extended by asking for which groups Θ(G) is a perfect graph or has other hereditary properties.
The explicit formulas for the named families provide test cases for conjectures about additional invariants such as the clique number or domination number of the same graph.

Load-bearing premise

The adjacency rule that connects two elements precisely when the gcd of their orders is 1 or a prime produces a graph whose structural properties reflect useful features of the underlying group.

What would settle it

A finite group G outside the characterized families for which Θ(G) is nevertheless a split graph, or a direct computation of the independence number for a cyclic or dihedral group that fails to match the paper's explicit formula.

Figures

Figures reproduced from arXiv: 2604.18475 by Ravi Ranjan, Shidra Jamil, Shubh Narayan Singh, Surbhi Kumari.

**Figure 1.** Figure 1: Graph H Observe that {1, 2, 3, 4} forms a maximum clique in H, so any independent set of H can contain at most one vertex from this clique. Moreover, vertex 1 is dominating in H. Consequently, the maximal independent sets of cardinality greater than one in H are precisely {2, 5}, {3, 5}, and {4, 5}. It follows that the maximal independent sets of cardinality greater than one in H(G) are precisely V [PITH_… view at source ↗

**Figure 2.** Figure 2: Graph H Observe that {1, 2, 3} forms a maximum clique in H, so any independent set of H can contain at most one vertex from this clique. Moreover, vertex 1 is dominating in H. Consequently, the maximal independent sets of cardinality greater than one in H are precisely {2, 4} and {3, 4}. It follows that the maximal independent sets of cardinality greater than one in H(G) are precisely V [PITH_FULL_IMAGE:f… view at source ↗

**Figure 3.** Figure 3: Graph H Observe that {1, 2, 3, 4} forms a maximum clique in H, so any independent set of H can contain at most one vertex from this clique. Moreover, vertex 1 is dominating in H. Consequently, the maximal independent sets of cardinality greater than one in H are precisely {2, 5, 7}, {3, 6, 7}, and {4, 5, 6, 7}. It follows that the maximal independent sets of cardinality greater than one in H(G) are precise… view at source ↗

read the original abstract

The prime-coprime graph $\Theta(G)$ of a finite group $G$ is the simple graph with vertex set $G$, where two distinct elements are adjacent whenever the greatest common divisor of their orders is either $1$ or a prime. We characterize all finite groups $G$ for which $\Theta(G)$ is a split graph. 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 several distinguished families of finite groups, including cyclic, dihedral, dicyclic, and semidihedral groups.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

This paper defines the prime-coprime graph on group elements and gives explicit independence numbers plus a split-graph characterization for standard families.

read the letter

The key takeaway is that this paper introduces the prime-coprime graph Θ(G) on the elements of a finite group G, with edges when the gcd of their orders is 1 or a prime number. They characterize exactly which groups make this graph a split graph, give a general lower bound on its independence number, and compute the exact value for cyclic, dihedral, dicyclic, and semidihedral groups. What stands out is the explicit work on those families. Getting closed-form expressions for the independence number in dihedral and semidihedral cases requires careful case analysis on element orders, and that kind of detail is useful for anyone who might apply these graphs later. The split graph characterization also seems to rest on straightforward arguments about cliques and independent sets in the graph. The paper does a decent job staying concrete. No heavy machinery beyond basic group theory and graph definitions. On the downside, the adjacency rule itself lacks strong motivation. Defining adjacency via that specific gcd condition produces the results they want, but it's not obvious why this is a natural choice compared to, say, just coprime orders or orders sharing a prime factor. The abstract presents it as the starting point without much discussion of why it captures something meaningful in group structure. The lower bound is general, but without seeing how close it gets to the actual values in the families, it's hard to judge its strength. This kind of paper belongs in a journal that publishes work on algebraic graph theory or finite group invariants. Readers who study parameters like independence numbers or chromatic numbers on group graphs will find the formulas handy. It doesn't reorganize the field, but the computations are new and verifiable. I would send it to peer review. The claims are specific enough that referees can check the derivations directly, and the new graph definition adds to the literature even if the motivation is light.

Referee Report

0 major / 3 minor

Summary. The paper defines the prime-coprime graph Θ(G) of a finite group G with vertex set G and edges between distinct elements a,b whenever gcd(o(a),o(b)) is 1 or a prime. It characterizes all finite groups G for which Θ(G) is a split graph, proves a general lower bound on the independence number α(Θ(G)) for arbitrary finite G, and computes α(Θ(G)) exactly for the families of cyclic, dihedral, dicyclic, and semidihedral groups.

Significance. If the results hold, the work supplies concrete structural information on a new graph invariant of finite groups, including a complete classification for the split-graph property and closed-form independence numbers for several standard families. These are standard but useful contributions in the area of graphs on groups; the explicit computations and the general lower bound are falsifiable and directly applicable to further classification problems.

minor comments (3)

[Section 3] The proof of the split-graph characterization (presumably the main theorem in Section 3) relies on case analysis over element orders; it would be helpful to include a brief remark on whether the argument extends immediately to groups with elements of composite order greater than 4 or if additional subcases are needed.
[Section 4] In the statement of the general lower bound (Theorem 4.1 or equivalent), the bound is expressed in terms of the number of elements of prime-power order; a short example computing the bound for a non-abelian group of order 12 would clarify its sharpness.
[Throughout] Notation for the independence number is consistent, but the paper occasionally uses α(G) and α(Θ(G)) interchangeably in the text; a single global definition at the beginning would prevent minor confusion.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We appreciate the referee's positive assessment of our work on the prime-coprime graph and the recommendation for minor revision. No major comments were provided in the report, therefore we have no specific responses to address at this time.

Circularity Check

0 steps flagged

No significant circularity identified

full rationale

The paper defines Θ(G) explicitly via the gcd condition on element orders (1 or prime) and derives a split-graph characterization, a general lower bound on independence number, and exact values for cyclic/dihedral/dicyclic/semidihedral groups via direct combinatorial arguments on group orders and element orders. No self-definitional reductions, fitted inputs renamed as predictions, or load-bearing self-citations appear in the claims; results are conditional on the stated adjacency rule and remain independent of the inputs.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 1 invented entities

The paper rests on the standard axioms of finite group theory and the newly introduced graph definition; no numerical parameters are fitted and no new entities beyond the graph itself are postulated.

axioms (2)

domain assumption G is a finite group
Explicitly stated in the abstract and required for the vertex set and order function to be well-defined.
domain assumption The adjacency rule uses gcd of element orders being 1 or prime
This is the core definition of Θ(G) given in the abstract.

invented entities (1)

prime-coprime graph Θ(G) no independent evidence
purpose: To encode order-gcd relations as edges and study independence number and split property
Newly defined in the paper; no independent evidence outside the definitions and derived results is supplied.

pith-pipeline@v0.9.0 · 5413 in / 1541 out tokens · 50918 ms · 2026-05-10T03:29:49.920575+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

19 extracted references · 1 canonical work pages

[1]

Adhikari and S

A. Adhikari and S. Banerjee. Prime coprime graph of a finite group.Novi Sad Journal of Mathematics, 52(2): 41–59, 2022

2022
[2]

D. M. Burton.Elementary Number Theory. McGraw-Hill, New York, 6th edition, 2007

2007
[3]

P. J. Cameron. Graphs defined on groups.International Journal of Group Theory, 11(2):53– 107, 2022

2022
[4]

P. J. Cameron and S. H. Jafari. On the connectivity and independence number of power graphs of groups.Graphs and Combinatorics, 36(3): 895–904, 2020

2020
[5]

Foldes and P

S. Foldes and P. L. Hammer. Split graphs. InProceedings of the 8th South-Eastern Conference on Combinatorics, Graph Theory and Computing, pages 311–315, 1977. 12 RA VI RANJAN, SHUBH N. SINGH, SURBHI KUMARI, SHIDRA JAMIL

1977
[6]

J. A. Gallian.Contemporary Abstract Algebra. Chapman and Hall/CRC, New York, 10th edition, 2021

2021
[7]

Hamm and A

J. Hamm and A. Way. Parameters of the coprime graph of a group.International Journal of Group Theory, 10(3): 137–147, 2021

2021
[8]

S. Hao, G. Zhong, and X. Ma. Notes on the co-prime order graph of a group.Proceedings of the Bulgarian Academy of Sciences, 75(3): 340–348, 2022

2022
[9]

James and M

G. James and M. Liebeck.Representations and Characters of Groups. Cambridge University Press, New York, 2nd edition, 2001

2001
[10]

Kumar, S

J. Kumar, S. Dalal, and V. Baghel. On the commuting graph of semidihedral group.Bulletin of the Malaysian Mathematical Sciences Society, 44(5): 3319–3344, 2021

2021
[11]

H. Li, G. Zhong, and X. Ma. Finite groups whose co-prime order graphs have positive genus. Proceedings of the Bulgarian Academy of Sciences, 75(9): 1270–1278, 2022

2022
[12]

X. Ma, R. Fu, and X. Lu. On the independence number of the power graph of a finite group. Indagationes Mathematicae, 29(2): 794–806, 2018

2018
[13]

R. P. Panda, S. Dalal, and J. Kumar. On the enhanced power graph of a finite group. Communications in Algebra, 49(4): 1697–1716, 2021

2021
[14]

Ranjan and S

R. Ranjan and S. N. Singh. On prime-coprime graphs of certain finite groups. Unpublished, available at https://arxiv.org/abs/2507.15993, 2025

work page arXiv 2025
[15]

Saini, S

M. Saini, S. M. S. Khasraw, A. Sehgal, and D. Singh. On co-prime order graphs of finite abelian p-groups.Journal of Mathematical and Computational Science, 11(6): 7052–7061, 2021

2021
[16]

Saini, V

M. Saini, V. Kumari, P. Rana, A. Sehgal, and D. Singh. Degree based matrices of co-prime order graph of finite groups.Mathematics and Statistics, 13(3): 127–135, 2025

2025
[17]

Saini, G

M. Saini, G. Singh, A. Sehgal, and D. Singh. On divisor labeling of co-prime order graphs of finite groups.Italian Journal of Pure and Applied Mathematics, 51: 443–451, 2024

2024
[18]

Sehgal, Manjeet, and D

A. Sehgal, Manjeet, and D. Singh. Co-prime order graphs of finite abelian groups and dihedral groups.Journal of Mathematics and Computer Science, 23(3): 196–202, 2021

2021
[19]

D. B. West.Introduction to Graph Theory. Prentice Hall, 2nd edition, 2001. Department of Mathematics, Central University of South Bihar, Gaya–824236, Bihar, India Email address:raviranjan23@cusb.ac.in Email address:shubh@cub.ac.in Email address:18sept.surbhi@gmail.com Email address:shidrajamil136@gmail.com

2001