On Structural Properties and Adjacency Spectrum of Coprime Graph of Integers
Subarsha Banerjee · 2025
Read On Structural Properties and Adjacency Spectrum of Coprime Graph of Integers by Subarsha Banerjee (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-2506-10583.txt.
Introduction
Subarsha Banerjee studies the coprime graph of the integers in a 2025 math paper, writing solo. In this graph, whole numbers up to a limit are dots, and two dots join when the numbers share no common factor but one. The paper probes the graph's shape and the spectrum of its adjacency matrix.
Banerjee finds bounds on how many links must be cut to split the graph and on how many crossings a drawing needs. The adjacency matrix always has determinant zero, and the count of its minus one and zero eigenvalues has floors. Its largest eigenvalue always tops two, the paper shows, with cases worked as proof.
Catalog record
| CREATOR | Subarsha Banerjee |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 31 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2506-10583
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
On Structural Properties and Adjacency Spectrum of Coprime Graph of Integers Subarsha Banerjee Abstract Let T C G n TCG_{n} denote the coprime graph having vertex set { 1 , 2 , … , n } \{1,2,\ldots,n\} with any two vertices i , j i,j being adjacent if and only if gcd ( i , j ) = 1 \gcd(i,j)=1 . In this article, we first study some structural properties of T C G n TCG_{n} . We study the vertex connectivity and crossing number of the coprime graph of integers. We discover a lower constraint on the multiplicity of − 1 -1 , which appears as an eigenvalue in the adjacency matrix of T C G n TCG_{n} . We demonstrate our findings with a variety of cases. We also show that the adjacency matrix of T C G n TCG_{n} is singular, i.e. has determinant 0 0 . Furthermore, we give a lower bound on the multiplicity of 0 0 , which appears as an eigenvalue in the adjacency matrix of T C G n TCG_{n} . Finally, we establish that the greatest eigenvalue of the adjacency matrix of T C G n TCG_{n} is always above 2 . 2. Keywords: coprime graph; vertex connectivity; integers; crossing number; adjacency spectrum; singular matrix; eigenvalue. 2020 Mathematics Subject Classification: 05C25, 05C50. 1 Introduction Let TCG_{n} be the coprime graph having vertex set \{1,2,\ldots,n\} , where any two vertices i,j are adjacent if and only if \gcd(i,j)=1 . Coprime graphs, presented by Erdös [ 2 ] in 1962, have sparked attention and research into various critical subjects. Erdös published a conjecture concerning subgraphs in coprime graphs in [ 2 ] , which sparked academic interest. Ahlswede and Khachatrian’s 1995 paper [ 9 ] responded negatively to the supposition. Ahlswede and Khachatrian conducted more research on this topic [ 10 , 11 ] . Newman suggested a conjecture about the criteria for perfect matching in coprime graphs, later proven by Pomerance and Selfridge in [ 12 ] . There are also other studies. Ahlswede and Blinovsky [ 13 ] examined extremal sets without coprime elements and sets of integers with pairwise common divisors. Erdös and Sarkozy [ 14 ] researched the cycle of coprime graphs, while Sander and Sander [ 15 ] investigated the kernel of coprime graphs. A survey [ 16 ] provides additional information on the research status of coprime graphs. In [ 23 ] , the authors determined the automorphism group, as well as the determining and resolving sets of coprime graphs. The concept of coprime graphs was generalized in [ 31 ] and further studied in [ 29 ] . The coprime graph of finite groups have also been an active research area. Many researchers have studied the coprime graphs of various finite groups recently, see for example, [ 17 , 18 , 19 , 20 , 21 , 22 ] . Inspired by the previously described studies, we investigate several structural properties of the coprime network of integers. Studying spectral properties of graphs associated with various algebraic structures has been an active topic of research, see [ 8 , 7 , 6 , 5 , 3 ] . Consequently, we also shed light on the coprime graph of integers’ adjacency eigenvalues. Section 2 is devoted to the basic concepts required for the sections that follow. We explore various structural characteristics of TCG_{n} in Section 3 . Lastly, we talk about the adjacency spectrum of TCG_{n} in Section 4 . 2 Preliminaries In this section, we present some preliminary theorems and definitions that we have utilized throughout the article. A graph G is represented by G=(V,E) where V denotes the vertex set of G and E denotes the edge set of G . Two vertices are considered to be adjacent if there is an edge between them. A complete graph with n vertices, denoted by K_{n} is a graph in which each pair of distinct vertices are adjacent. A path P of length k in a graph G is an alternating sequence of vertices and edges v_{0},e_{0},v_{1},e_{1},v_{2},e_{2},\ldots,v_{k-1},e_{k-1},v_{k} , where v_{i}^{\prime}s are unique vertices, and e_{i} is the edge joining v_{i} and v_{i+1} . If v_{0}=v_{k} , P is considered a cycle with length k . The girth refers to the length of the shortest cycle in G . A graph G is considered connected if there is a path connecting any two vertices u,v\in V . The term disconnected graph refers to a graph that is not connected. In a connected graph G , the distance between two vertices u,v , indicated by d(u,v) , is the length of the shortest path between u and v . The diameter of a connected graph G is defined as diam (G)=\max\{d(u,v):u,v\in V\} . A planar graph can be immersed in the plane, meaning its edges intersect only at their endpoints. The crossing number of a graph G denoted by \text{cr}(G) is the minimal number of edge crossings in a planar drawing of G . If the graph is planar, then its crossing number is 0 . The crossing number of the complete graph K_{n} and complete bipartite graph K_{m,n} are still not known for all m,n . Several problems on crossing number of a graph have been discussed in [ 26 ] . Finding the crossing number of a graph is an NP-complete problem [ 25 ] . Readers may refer to [ 24 ] for a survey on the crossing number of a graph. The vertex connectivity \kappa(G) of a graph G is the least number of vertices that may be removed to create a disconnected graph. We define a disconnected graph’s connectivity as 0 . A triangulated graph has an edge connecting two non-adjacent vertices in each cycle of length four or more. A graph’s clique number refers to the size of its greatest complete subgraph. A graph is said to be bipartite if its vertex set can be partitioned into two disjoint sets P and Q such that any edge in the graph will have one of its end-points in A , and the other in B . A complete bipartite graph denoted by K_{m,n} is a special kind of bipartite graph in which there exists an edge between every vertex of P and every vertex of Q . The adjacency matrix of a graph having vertices v_{1},v_{2},\dots,v_{n} is an n\times n matrix whose (i,j)^{\text{th}} entry is 1 if there is an edge between v_{i} and v_{j} and it is 0 otherwise. The adjacency matrix of G is denoted by A(G) , and it is a symmetric matrix. Consequently, the eigenvalues of A(G) are real numbers. Let the eigenvalues of A(G) be denoted by \lambda_{1}\leq\lambda_{2}\leq\lambda_{3}\leq\cdots\leq\lambda_{n-1}\leq\lambda_{n} . The largest eigenvalue of A(G) , i.e. \lambda_{n} is known as the spectral radius of G . The remaining results in the paper depend on the following theorems. Theorem 2.1 . [ 1 , Theorem 6.2.2 ] [ Kuratowski’s Theorem ] A graph is planar if and only if it does not contain a subdivision of K_{5} or K_{3,3} . Theorem 2.2 . [ 4 ] [ Eigenvalue