Some Necessary and Sufficient Conditions for Diophantine Graphs
2024
Read Some Necessary and Sufficient Conditions for Diophantine Graphs (2024) 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-2412-20562.txt.
Description
A 2024 arXiv research paper by . A linear Diophantine equation a x + b y = n ax+by=n is solvable if and only if gcd ( a , b ) \gcd(a,b) divides n n . A graph G G of order n n is called Diophantine if there exists a labeling function f f of vertices such that gcd ( f ( u ) , f ( v ) ) \gcd(f(u),f(v)) divides n n for every two adjacent vertices u , v u,v
Catalog record
| YEAR | 2024 |
|---|---|
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 37 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2412-20562
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Some Necessary and Sufficient Conditions for Diophantine Graphs Abstract A linear Diophantine equation a x + b y = n ax+by=n is solvable if and only if gcd ( a , b ) \gcd(a,b) divides n n . A graph G G of order n n is called Diophantine if there exists a labeling function f f of vertices such that gcd ( f ( u ) , f ( v ) ) \gcd(f(u),f(v)) divides n n for every two adjacent vertices u , v u,v in G G . In this work, maximal Diophantine graphs on n n vertices, D n D_{n} , are defined, studied and generalized. The independence number, the number of vertices with full degree and the clique number of D n D_{n} are computed. Each of these quantities is the basis of a necessary condition for the existence of such a labeling. M. A. Seoud* 3 , A. Elsonbaty* 2 , A. Nasr* 1 , M. Anwar* 4 *Department of Mathematics, Faculty of Science, Ain Shams University, 11566, Abbassia, Cairo, Egypt. e-mails: 1 [email protected] , 2 [email protected] , 3 [email protected] , 4 [email protected] , MSC code: 05A10, 05C07, 05C78, 11A05, 11A25, 11B75, 11D04, 11D88. Keywords : Diophantine graph, Maximal Diophantine graph, labeling isomorphism, \gamma -labeled graph. 1 Introduction Assuming that a graph G=(V,E) is a finite simple undirected graph with |V| vertices and |E| edges, where V=V(G) is the vertex set, E=E(G) is the edge set, |V| is called the order of the graph G and |E| is called the size of the graph G . In general, |X| denotes the cardinality of a set X . \delta(G) denotes the minimum degree of the vertices in a graph G . A set of vertices S of a graph G is said to be an independent set or a free set if for all u,v\in S , u,v are nonadjacent in G . The independence number, denoted by \alpha(G) , is the maximum order of an independent set of vertices of a graph G . The operation of adding an edge e=uv to a graph G joining the vertices u,v yields a new graph with the same vertex set V(G) and edge set E(G)\cup\{uv\} , which is denoted G+\{uv\} . The operation of deleting an edge e=uv from a graph G removes only that edge, the resulting graph is denoted G-\{uv\} . A spanning subgraph of a graph G is a subgraph of G obtained by deleting edges only, adding edges to a graph G yields a spanning supergraph of G . The join of two graphs G and H is denoted by G+H , it has the following vertex set V(G+H)=V(G)\cup V(H) and edge set E(G+H)=E(G)\cup E(H)\cup\{uv:u\in V(G)\ \mbox{and}\ v\in V(H)\} . K_{n},\overline{K_{n}} and C_{n} denote the complete graph, the null graph and the cycle graph of order n respectively. We follow terminology and notations in graph theory as in A. Bickle [ 2 ] , J. L. Gross; J. Yellen; P. Zhang [ 5 ] , F. Harary [ 6 ] and K. H. Rosen [ 11 ] . The concept of prime labeling was introduced by R. Entringer and was discussed in a paper by A. Tout [ 14 ] . A graph G is called a prime graph if there exists a bijective map f:V\rightarrow\{1,2,\dots,n\} such that for all uv\in E , (f(u),f(v))=1 . Some authors investigated algorithms for prime labeling in [ 4 ] and necessary and sufficient conditions are studied in [ 12 ] , [ 13 ] . The notion of Diophantine labeling is an extension of that of prime labeling. In this paper, we give a brief summary of some definitions and some results pertaining to Diophantine graphs. A generalization encompassing prime graphs, Diophantine graphs and another type of graph labeling is introduced and discussed. In maximal Diophantine graphs, an arithmetic function is established to calculate the number of vertices with full degree and the order of the maximal clique or the maximal complete subgraph, the independence number is computed and necessary and sufficient conditions are provided with these bounds. Moreover, an explicit formula for a vertex with minimum degree and minimum label is proved. Furthermore, a new perspective on degree sequences for establishing necessary conditions is presented. Relevant definitions and notations from number theory are mentioned. We follow the basic definitions and notations of number theory as in T. M. Apostol [ 1 ] and D. Burton [ 3 ] . This manuscript is structured as follows. Section 2 provides some results of \gamma -labelings. Section 3 is partitioned into three subsections, each presents some results related to maximal Diophantine graphs. Subsection 3.1 discusses some basic bounds and necessary and sufficient conditions for maximal Diophantine graphs. Subsection 3.2 and 3.3 provided some necessary conditions and explore properties of the minimum degree and the degree sequence in maximal Diophantine graphs. Section 4 includes some examples of non-Diophantine graphs to explain the relation among these necessary conditions. Definition 1.1 . [ 8 ] Let G be a graph with n vertices. The graph G is called a Diophantine graph if there exists a bijective map f:V\rightarrow\{1,2,\dots,n\} such that for all uv\in E , (f(u),f(v))\mid n . Such a map f is called a Diophantine labeling of G . A maximal Diophantine graph with n vertices, denoted by (D_{n},f) , is a Diophantine graph such that adding any new edge yields a non-Diophantine graph. If there is no ambiguity, we drop f from (D_{n},f) and write it simply D_{n} . Clearly, if a graph G is Diophantine, then |E(G)|\leq|E(D_{n})| . A formula that computes the number of edges of D_{n} can be found in [ 8 ] . Some maximal Diophantine graphs are given in the next example. Example 1.1 . The following three graphs are examples of maximal Diophantine graphs. 9 1 7 5 3 2 4 6 8 (a) Graph D_{9} 4 1 2 10 7 5 8 3 6 9 (b) Graph D_{10} 9 1 11 7 5 3 2 4 6 8 10 (c) Graph D_{11} Figure 1 : Some maximal Diophantine graphs D_{9} , D_{10} and D_{11} Definition 1.2 . [ 8 ] For a given an integer n\in\mathbb{Z}^{+} and a prime p\in\mathbb{P} , the successor of the p -adic valuation is denoted by \acute{v}_{p}(n):=v_{p}(n)+1 , where v_{p}(n) is the p -adic valuation, \mathbb{Z}^{+} is set of positive integers and \mathbb{P} is the set of prime numbers. The number p^{\acute{v}_{p}(n)} is called the critical prime power number with respect to p,n . In the rest of this paper, the following arithmetic functions \pi,\omega and \tau will be used, (see [ 1 ] , [ 3 ] ): Let n\in\mathbb{Z}^{+} . \pi(n):=\big|\{p\in\mathbb{P}:2\leq p\leq n\}\big|,\quad\omega(n):=\big|\{p\in\mathbb{P}:p\mid n,\ 2\leq p\leq n\}\big|,\quad\tau(n):=\big|\{d\in\mathbb{Z}^{+}:d\mid n\}\big|. Lemma 1.1 . [ 8 ] Suppose D_{n} is a maximal Diophantine graph of order n . For every u,v\in V(D_{n}) , uv\notin E(D_{n}) if and only if there exists p\in\mathbb{P} such that f(u),f(v)\in M_{p^{\acute{v}_{p}(n)}}:=\left\{kp^{\acute{v}_{p}(n)}:\ k=1,2,\dots,\left\lfloor\frac{n}{p^{\acute{v}_{p}(n)}}\right\rfloor\right\}. Theorem 1.1 . [ 8 ] Suppose D_{n} is a maximal Diophantine graph of order n . For every u\in V(D_{n}) , \deg(u)=n-1\quad\mbox{if and only if}\quad f(u)\mid n\quad\mbox{{or}}\quad\frac{n}{2}<f(u)=p^{\acute{v}_{p}(n)}<n, where p\in\mathbb{P} and the exclusive or will