Which coprime graphs are divisor graphs?

Xuanlong Ma, Liangliang Zhai, Nan Gao School of Science, Xi’an Shiyou University, Xi’an 710065, P.R. China · 2025

Read Which coprime graphs are divisor graphs? by Xuanlong Ma, Liangliang Zhai, Nan Gao School of Science, Xi’an Shiyou University, Xi’an 710065, P.R. China (2025) 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-2501-14339.txt.

Introduction

Xuanlong Ma and co-authors classify when the coprime graph of a finite group is also a divisor graph, in a 2025 mathematics paper. A group's coprime graph joins elements whose orders share no prime factor, while divisor graphs come from divisibility patterns among integers. The team first settles which generalized lexicographic products count as divisor graphs.

That groundwork shows power graphs, reduced power graphs, and order graphs all qualify. The coprime graph itself is such a product, and the authors pin down exactly which groups pass the test. The settled cases include nilpotent, dihedral, symmetric, alternating, and sporadic simple groups, plus groups with at most four prime divisors. The results tie group structure to graph form.

Catalog record

CREATORXuanlong Ma, Liangliang Zhai, Nan Gao School of Science, Xi’an Shiyou University, Xi’an 710065, P.R. China
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE42 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2501-14339

Browse the full library · About the Tower of Babel

Full text

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

Which coprime graphs are divisor graphs? Xuanlong Ma, Liangliang Zhai, Nan Gao School of Science, Xi’an Shiyou University, Xi’an 710065, P.R. China Abstract For a finite group G G , the coprime graph Γ ⁡ ( G ) \Gamma(G) of G G is a graph with vertex set G G , in which two distinct vertices a a and b b are adjacent if the order of a a and the order of b b are coprime. In this paper, we first give a characterization for which generalized lexicographic products are divisor graphs. As applications, we show that every of power graph, reduced power graph and order graph is a divisor graph, which also implies the main result in [N. Takshak, A. Sehgal, A. Malik, Power graph of a finite group is always divisor graph, Asian-Eur. J. Math. 16 (2023), ID: 2250236]. Then, we prove that the coprime graph of a group is a generalized lexicographic product, and give two characterizations for which coprime graphs are divisor graphs. We also describe the groups G G with | π ⁡ ( G ) | ≤ 4 |\pi(G)|\leq 4 , whose coprime graph is a divisor graph. Finally, we classify the finite groups G G so that Γ ⁡ ( G ) \Gamma(G) is a divisor graph if G G is a nilpotent group, a dihedral group, a generalized quaternion group, a symmetric group, an alternating group, a direct product of two non-trivial groups, and a sporadic simple group. Key words: Coprime graph; Divisor graph; Finite group 2020 MSC: 05C25 † † E-mail addresses: [email protected] (X. Ma), [email protected] (L. Zhai), [email protected] (N. Gao) 1 Introduction The study of graph representations of an algebraic structure is a popular and interesting research topic in the field of algebraic graph theory. For example, a well-known graph representation for group is the Cayley graph, which has a very long history. Moreover, graphs from algebraic structures have been actively investigated in the literature, since they have some valuable applications, see [ 17 , 19 ] . Given a group G , one can define various graphs on G . Among a number of graphs defined on the group G reflecting some algebraic properties of G , apart form Cayley graph, two which have been studied widely are the following: • the commuting graph of G , which was first introduced by Brauer and Fowler [ 5 ] ; • the power graph of G , denoted by \mathcal{P}(G) , is a graph with vertex set G , and two distinct vertices are adjacent if one is a power of the other. In 2000, Kelarev and Quinn [ 18 ] first introduced the concept of a power graph defined on a group, which is a directed graph. In 2009, Chakrabarty et al. [ 6 ] introduced the concept of an undirected power graph. Afterwards, the term power graph always means an undirected power graph (cf. [ 1 ] ). Because the order of an element is one of the most basic and important concepts in group theory, one can define a graph over a group by element order. The order graph \mathcal{S}(G) of G is an undirected graph with vertex set G , and two distinct vertices x,y are adjacent if o(x)|o(y) or o(y)|o(x) . In 2017, Hamzeh and Ashrafi [ 15 ] first introduced the order graph of a group and called this graph as the main supergraph of \mathcal{P}(G) . Clearly, if two vertices a and b are adjacent in \mathcal{P}(G) , then a and b also are adjacent in \mathcal{S}(G) . This means that \mathcal{P}(G) is a spanning subgraph of \mathcal{S}(G) . In [ 21 ] , the authors introduced the concept of a coprime graph of a group. For a group G , the coprime graph of G , denoted by \Gamma(G) , is the undirected graph with vertex set G and two distinct vertices x,y are adjacent if and only if o(x) and o(y) are relatively prime, that is, (o(x),o(y))=1 , where o(x) and o(y) are the orders of x and y , respectively. The authors in [ 21 ] explored how the properties of graphs can effect on the properties of groups. Dorbidi [ 10 ] showed that, for any finite group G , the clique number of \Gamma(G) is equal to the chromatic number of \Gamma(G) , and classified the groups whose coprime graph is complete r -partite or planar. Selvakumar and Subajini [ 27 ] classified the finite groups whose coprime graph has (non)orientable genus one. Hamm and Way [ 14 ] gave the exact value of the independence number of the coprime graph of a dihedral group and studied the finite groups whose coprime graph is perfect. Alraqad et al. [ 3 ] obtained all finite groups whose coprime graph has precisely 3 end-vertices. All graphs considered in this paper are simple graph, without loops and multiple edges. Let \Gamma be a graph. Denote by V(\Gamma) and E(\Gamma) the vertex set and edge set of \Gamma , respectively. An orientation D of an undirected graph \Gamma is an assignment of exactly one direction to each of the edges of \Gamma . A transmitter of this orientation D is a vertex having indegree 0 and a receiver of D is a vertex having outdegree 0 . A vertex b of D is transitive provided that its outdegree and indegree are both greater than zero, and (a,b),(b,c)\in E(D) must imply (a,c)\in E(D) , where a,c\in V(D) and (a,b)\in E(D) means that there is a directed edge from a to b in D . A graph labeling of a graph is an assignment of integers to the vertices or edges or both, subject to certain conditions have been motivated by practical problems. Labeled graphs serve useful mathematical models for a broad range of applications, such as, satellite communication through [ 23 ] and life sciences [ 12 ] . In 2000, Singh and Santhosh [ 28 ] first introduced the concept of a divisor graph. A divisor graph \Gamma is a simple graph with V(\Gamma) as a subset of the set of positive integers, and any two distinct x,y\in V(\Gamma) , \{x,y\}\in E(\Gamma) if and only if either x\mid y or y\mid x . A graph which is isomorphic to a divisor graph is also called a divisor graph . That is to say, if \Gamma is a divisor graph, then there exists an injection \alpha from V(\Gamma) to the set of positive integers such that \Gamma is isomorphic to the divisor graph with vertex set \alpha(V(\Gamma)) , where \alpha is called a divisor labeling of \Gamma . In 2001, Chartrand et al. [ 7 ] studied the following question: Question 1.1 Which graphs are divisor graphs? Specifically, they showed that, a graph \Gamma is a divisor graph if and only if there exists an orientation D of \Gamma such that every vertex of D is a transmitter, a receiver, or a transitive vertex. Afterward, Frayer [ 13 ] also studied Question 1.1 and showed that for a divisor graph \Gamma with a transitive vertex, \Gamma\times\Delta is a divisor graph if and only if E(\Delta)=\emptyset . In 2006, Vinh proved that a

Read the complete text