The sum graph \(G^{+}(S)\) of a finite subset \(S\subset \mathbb{N}\)={1,2,3,…} is the graph (V,E) where V=S and \(uv\in\)E if and only if \(u+v\in\) S. This concept was introduced by Harary [9], where some basic properties of the family of all sum graphs were presented. In [10], Harary extended this definition into an integral sum graph and proposed some open problems. Motivated by these definitions, we introduce a graph called perfect difference graph. We investigate the properties of this family of graphs.
The available tools in Graph Theory can be used to investigate the structure imposed on the Natural numbers by various relations. The sum graph \(G^{+}(S)\) of a finite subset \(S\subset \mathbb{N}\)={1,2,3,…} is the graph \((V,E)\) where \(V=S\) and \(uv\in\) E if and only if \(u+v\in\) S. This concept was introduced by Harary [9], where some basic properties of the family of all sum graphs were presented. In [10], Harary extended this definition and studied sum graphs over all the integers so that \(S\) contains positive or negative integers or zero. A graph so obtained is called an integral sum graph. The integral sum number \(\sigma\)(G) of a graph G was defined as the smallest number of isolated vertices which when added to G result in a sum graph. In [10], Harary found the integral sum number of the small graphs and offered several intriguing unsolved problems. Santhosh and Suresh Singh [13] determined the value of \(\sigma\)(G) for certain graphs. Nicholas et al. [12] solved some open problems posed by Harary in [10]. Ghodasara and Patel [8] introduced square sum graphs. A graph \(G=(V,E)\) with \(p\) vertices and \(q\) edges is said to be square sum graph, if there exists a bijective mapping \(f: V(G)\rightarrow \{0,1,2,…,p-1\}\) such that the induced function \(f^*:E(G)\rightarrow \mathbb{N}\) defined by \(f^*(uv)=(f(u))^2+(f(v))^2\) for every \(uv\in E(G)\) is injective. A graph with square sum labeling is called square sum graph. They proved certain families of square sum graph. Chandrashekar Adiga, Ramaswamy and Somashekhara [2] introduced strongly multiplicative graphs. A graph with \(p\) vertices is said to be strongly multiplicative if its vertices can be labelled \(1,2,…,p\) so that the values of labelings of their end vertices are all distinct. They proved the existence of certain strongly multiplicative graphs. Graphs constructed using the set of vertices \(V=\{1,2,…,p\}\) and number theoretic operations focus on properties like divisibility, coprimality and common divisors to define edges. These graphs reveal structural insights into the behaviour of integers. There are many number theoretic graphs like Arithmetic graphs [1], Divisor graphs [6][14], Relatively Prime graphs [7], Mobius function graphs [4] and so on. Motivated by these definitions, we introduce a graph called Perfect Difference graph. Most of the papers discussed the existence of a particular type of labeling for certain graphs. In this paper, we investigate the Eulerian, Hamiltonian, connectedness and planarity properties of perfect difference graphs.
For all terms and definitions, not defined specifically in this paper, we refer to [3] and [5]. For implementation of Python code, we refer to [11].
In this section, we define perfect difference graphs and study the degree sequence, maximum and minimum degrees of this graph.
Definition 2.1. Let \(\mathbb{N}\) be the set of all natural numbers \(1,2,3,…\) and for each positive integer \(n\ge2\), let \(Q_n=\{k^2/ k\in\mathbb{N}, 1\le k\le \left\lfloor \sqrt{n-1}\right\rfloor\}.\) We form a simple, undirected graph \(G=(V,E)\) whose vertex set is \(V=\{1,2,…,n\}\) and \((x,y)\in E\) if and only if \(|x-y|\in Q_n.\) The graph \(G\) is called the perfect difference graph and is denoted by \(D^2(n).\)
Example 2.2. For \(D^2(6),\) take\(\ V=\{1,2,3,4,5,6\} \ ; \ E=\{(1,2),(2,3),(3,4),(4,5),(5,6),\\ (1,5),(2,6)\}.\)
Observation 2.3. (a) For every pair of vertices of the form (v,v+1) there is an edge in \(D^2(n)\).
(b) \(D^2(n)\) is a subgraph of \(D^2(n+1)\).
Theorem 2.4. Degree of any vertex v in G=\(D^2(n)\) is \(\left\lfloor \sqrt{v-1} \right\rfloor +\left\lfloor \sqrt{n-v}\right\rfloor.\)
Proof. Consider a vertex v in G. By the definition of adjacency of v, v shares an edge with a vertex in \(\{1,2,…,n\}-\{v\}\) whenever,\[1\le v-l^2 \le n \ \text{and} \ 1 \le v+r^2 \le n, \ \text{for some} \ l,r \in \mathbb{N},\] \[\text{(i.e.,)} \ 1\le l \le \sqrt{v-1} \ \text{and} \ 1\le r \le \sqrt{n-v}.\]
Hence, \(deg_G(v)=\left\lfloor \sqrt{v-1} \right\rfloor +\left\lfloor \sqrt{n-v}\right\rfloor.\) \(\square\)
From this theorem, we can determine the degree sequence of G=\(D^2(n)\)
Proposition 2.5. \(\Delta(D^2(n))=\left\lfloor 2\sqrt{\frac{n-1}{2}}\right\rfloor.\)
Proof. For any vertex \(v\), \(deg_G(v)=\left\lfloor \sqrt{v-1} \right\rfloor +\left\lfloor \sqrt{n-v}\right\rfloor.\) Since \(\left\lfloor x \right\rfloor \leq x\), we consider \[\begin{aligned} f(x) & = \sqrt{x-1}+\sqrt{n-x},\\ f'(x) & = \frac{1}{2\sqrt{x-1}} – \frac{1}{2\sqrt{n-x}}, \end{aligned}\] \[f'(x) = 0 \implies x = \frac{n+1}{2} \text{ and } f”(\frac{n+1}{2}) < 0.\]
Therefore, \(\max f(x) = \sqrt{\frac{n+1}{2}-1} + \sqrt{n – \frac{n+1}{2}} = 2\sqrt{\frac{n-1}{2}}\).
Now consider the function, \[g(v) =\left\lfloor\sqrt{v-1}\right\rfloor + \left\lfloor\sqrt{n-v}\right\rfloor \ \ \ (v\in\{1,2,…,n\})\] \[g(v) \le\sqrt{v-1} + \sqrt{n-v} =f(v) \le 2\sqrt{\frac{n-1}{2}}.\]
Since \(g(v)\) is an integer, we have \[g(v)\le\left\lfloor2\sqrt{\frac{n-1}{2}}\right\rfloor.\]
For each positive integer \(n\), we can find an integer \(1\le v^*\le n\) such that \(g(v^*)=\left\lfloor2\sqrt{\frac{n-1}{2}}\right\rfloor\). For example, if \(n=2m+1\), then we can take \(v^*=m\). If \(n=2m\), then we can take \(v^*=m-1\) or \(m\) or \(m+1\) (depending on \(n\)) such that\(g(v^*)=\left\lfloor2\sqrt{\frac{n-1}{2}}\right\rfloor\).
Hence \(\Delta(D^2(n)=\left\lfloor 2\sqrt{\frac{n-1}{2}}\right\rfloor.\) \(\square\)
Proposition 2.6. \(\delta(D^2(n)=\left\lfloor\sqrt{n-1}\right\rfloor\).
Proof. By Theorem 2.4, \(deg_G(1)=deg_G(n)=\left\lfloor\sqrt{n-1}\right\rfloor.\)
Let us show that interior vertices \(2\le v \le n-1\) cannot give a smaller value than the value at the end points. For an interior vertex \(v\), when \(v\) increases, \(\left\lfloor\sqrt{v-1}\right\rfloor\) is non-decreasing and \(\left\lfloor\sqrt{n-v}\right\rfloor\) is non-increasing. For symmetric internal vertices \(1+k\) and \(n-k\), we have \[deg_G(1+k)=\left\lfloor\sqrt{k}\right\rfloor+\left\lfloor\sqrt{n-k-1}\right\rfloor,\] and \[deg_G(n-k)=\left\lfloor\sqrt{n-k-1}\right\rfloor+\left\lfloor\sqrt{k}\right\rfloor=deg_G(1+k).\]
Thus the function \(deg_G(v)\) is symmetric about the midpoint.
Also we observe that \[deg(2)=deg(n-2)\ge \sqrt{n-1}, \ \text{since} \ 1+\left\lfloor\sqrt{n-2}\right\rfloor\ge\left\lfloor\sqrt{n-1}\right\rfloor.\]
Therefore for any \(2\le v\le n-1, deg_G(v)\ge\left\lfloor\sqrt{n-1}\right\rfloor\).
Hence \(\delta(D^2(n)=\left\lfloor\sqrt{n-1}\right\rfloor.\) \(\square\)
Example 2.7. When \(n=8, \Delta = \left\lfloor2\sqrt{\frac{7}{2}}\right\rfloor=3, \delta=\left\lfloor\sqrt{8-1}\right\rfloor=2.\)
In this section, we check for what values of n, \(D^2(n)\) is complete / a path / a cycle / a tree and for what values of n, \(D^2(n)\) contains \(K_3\).
Obviously \(D^2(n)\) contains \(K_1\) for all n and \(D^2(n)\) contains \(K_2\) for all \(n\ge2.\) We prove that \(D^2(n)\) contains \(K_3\) if and only if \(n\ge26.\)
Proposition 3.1. \(D^2(n)\) is complete, if and only if \(n\le2\).
Proof. Let the graph\(D^2(n)\) be complete and \(n>2\). Then the edge set of \(D^2(n)\) does not contain the edge (1,3). Therefore \(D^2(n)\) is not complete.
The converse part is trivial since \(D^2(1)\equiv K_1\) and \(D^2(2)\equiv K_2.\) \(\square\)
Theorem 3.2. \(K_3\) is a subgraph of \(D^2(n)\), if and only if \(n\ge26.\)
Proof. If \(K_3\) is a subgraph of \(D^2(n)\), then there exists three vertices a,b,c where \(1\le a<b<c\le n\) such that, \(\lvert a-b \vert = {l_1}^2, \ \lvert b-c \vert = {l_2}^2, \ \lvert c-a \vert = {l_3}^2,\) for some \(l_1,l_2,l_3\in \mathbb{N}.\)
By our assumption, \(a<b<c\).
Therefore, \[\begin{aligned} b-a&=l_1^2 \\ c-b&=l_2^2 \\ c-a&=l_3^2. \end{aligned}\]
Eliminating a, b and c from the above three equations, we get, \(l_1^2+l_2^2=l_3^2\).
Therefore \((l_1,l_2,l_3)\) forms a Pythagorean triple. The smallest possible hypotenuse in a Pythagorean triple is \(l_3=5\), hence \(c-a\ge25\) and hence \(c\ge a+25\ge 26.\) Thus \(n\ge26.\)
Conversely, Suppose \(n\ge26\). Then the vertices “\(1\)“,“\(10\)”, and “\(26\)” form a complete graph on \(3\) vertices in \(D^2(n)\). \(\square\)
Observation 3.3. Clique number of \(D^2(n)\) is \(3\) if and only if \(26\le n \le 4,85,809.\)
We have verified this fact by using a Python program, we have also verified that the smallest value of \(n\) for which \(D^2(n)\) contains \(K_4\) is \(4,85,810\). [Refer Appendix I](The coding uses no data set). Thus \(K_4\) is a subgraph of \(D^2(n)\) if and only if \(n \ge 4,85,810.\) In this case the vertices of \(K_4\) are “\(1\)”, “\(23,410\)”,“\(34,226\)” and “\(4,85,810\)” as shown in Figure 3.
The problems of finding \(n\) for which \(D^2(n)\) contains \(K_m; \ m\ge5\) is still an open problem.
Theorem 3.4. The Perfect Difference graph \(D^2(n)\) is a path \(P_n\), if and only if n \(\le 4\).
Proof. Let \(n>4\) and the graph \(D^2(n)\) be path. Then the Perfect Difference graph always has an edge \((1,5)\). Also there is an edge between the vertices of the form \(v\) and \(v+1,\) the edge set contains the subset \(\{(1,2),(2,3),(3,4),…\}\).
Thus the cycle \(C_5\) is a subgraph of all the graphs \(D^2(n),\ n>4\).
Hence, \(D^2(n)\) is not a path (a contradiction).
Conversely, we shall show that if \(n\le\)4, then \(D^2(n)\) is a path since, \[D^2(1)\equiv K_1, D^2(2)\equiv P_2, D^2(3)\equiv P_3, D^2(4)\equiv P_4.\] \(\square\)
Theorem 3.5. \(D^2(n)\) is a cycle, if and only if n=5.
Proof. Let n\(\ne\)5 and \(D^2(n)\) be a cycle.
Case (i) n\(<5\).
By the above theorem, when n\(<\)5, \(D^2(n)\) forms a path. Hence, \(D^2(n)\) is not a cycle for \(n<5\).
Case (ii) n\(>\)5.
In this case, \(n\ge6\) and \(deg_G(2)=\left\lfloor 1 \right\rfloor+\left\lfloor \sqrt{n-2}\right\rfloor\ge 3\) and so the graph \(D^2(n)\) is not 2-regular.
Therefore, \(D^2(n)\) is not a cycle for \(n>5\).
Conversely, let n=5. Then \(1-2-3-4-5-1\) is the cycle. \(\square\)
Theorem 3.6. \(D^2(n)\) is a tree, if and only if n\(\le4\).
Proof. Let \(D^2(n)\) be a tree and n\(>\)4.
By Theorem 3.5, there exists a cycle in every Perfect Difference graph \(D^2(n)\) where n\(\ge\)5. G=\(D^2(n)\) contains a cycle, thus contradicting the definition of a tree.
Therefore, \(D^2(n)\) is not a tree for n\(>\)4.
Conversely, let n\(\le\)4. By Theorem 3.4, \(D^2(n)\) is a path and hence a tree. \(\square\)
In this section we discuss the values of n for which \(D^2(n)\) is Eulerian or Hamiltonian. Also we discuss the connectedness and planarity of \(D^2(n)\).
Lemma 4.1. There exists a pair of vertices \((v,v+1)\) in \(D^2(n)\) such that its absolute value of degree difference between them is \(1\) for n\(>5\).
Proof. Case 1. \(n-1\ne a^2\) for any \(a \in \mathbb{N}\).
Consider the pair of vertices (1,2). \[\begin{aligned} deg_G(1)&=\left\lfloor \sqrt{n-1}\right\rfloor+\left\lfloor \sqrt{1-1}\right\rfloor\\ &=\left\lfloor \sqrt{n-1}\right\rfloor.\\ deg_G(2)&=\left\lfloor \sqrt{n-2}\right\rfloor+\left\lfloor \sqrt{2-1}\right\rfloor\\ &=\left\lfloor \sqrt{n-2}\right\rfloor+\left\lfloor \sqrt{1}\right\rfloor\\ &=\left\lfloor \sqrt{n-2}\right\rfloor+1. \end{aligned}\]
\(deg_G(1)-deg_G(2)=\left\lfloor \sqrt{n-1}\right\rfloor-\left\lfloor \sqrt{n-2}\right\rfloor-1\).
We know that, \(\left\lfloor \sqrt{n}\right\rfloor-\left\lfloor \sqrt{n-1}\right\rfloor =\begin{cases} 0, \text{if n is not a perfect square},\\ 1, \text{otherwise}. \end{cases}\)
Hence, \(deg_G(1)-deg_G(2)=0-1=-1\)(Since \(n-1\) is not a perfect square).
Therefore, \(\vert deg_G(1)-deg_G(2) \vert=1\).
Case 2. \(n-1= a^2\) for some \(a \in \mathbb{N}\) and \(n> 5\).
In this case, \(deg_G(1)-deg_G(2)=\left\lfloor \sqrt{n-1}\right\rfloor-\left\lfloor \sqrt{n-2}\right\rfloor-1=1-1=0.\)
Hence we are in need of another pair of vertices \((v,v+1)\) to justify our statement.
For instance, consider \((v,v+1)=(4,5)\).Then, \[\begin{aligned} deg_G(4)&=\left\lfloor \sqrt{n-4}\right\rfloor+\left\lfloor \sqrt{4-1}\right\rfloor\\ &=\left\lfloor \sqrt{n-4}\right\rfloor+1.\\ deg_G(5)&=\left\lfloor \sqrt{n-5}\right\rfloor+\left\lfloor \sqrt{5-1}\right\rfloor\\ &=\left\lfloor \sqrt{n-5}\right\rfloor+\left\lfloor \sqrt{4}\right\rfloor\\ &=\left\lfloor \sqrt{n-5}\right\rfloor+2. \end{aligned}\]
\(deg_G(4)-deg_G(5)=\left\lfloor \sqrt{n-4}\right\rfloor+1-\left\lfloor \sqrt{n-5}\right\rfloor-2\\ =\left\lfloor \sqrt{n-4}\right\rfloor-\left\lfloor \sqrt{n-5}\right\rfloor-1\\\) Our aim is to check whether \(n-4\) is a perfect square for \(n>5\) and \(n-1=a^2\). Suppose \(n-4=b^2\), for some \(b \in \mathbb{N}\). Then, \[\begin{aligned} b^2&=n-4\\&=(n-1)-3\\b^2&=a^2-3\\ a^2-b^2&=3. \end{aligned}\]
Therefore \(a=\pm 2,\ b=\pm 1\). Hence, \(n-1=(\pm 2)^2=4\Rightarrow n=5\), which is the exception.
Therefore, \(n-4\) is not a perfect square, if \(n-1\) is a perfect square.
This implies \(\left\lfloor \sqrt{n-4}\right\rfloor-\left\lfloor \sqrt{n-5}\right\rfloor=0\).
Hence, \(\vert deg_G(4)-deg_G(5) \vert=1\).
Thus this lemma proves the existence of pair of vertices of the form \((v,v+1)\) such that \(\vert deg_G(v)-deg_G(v+1) \vert=1.\) \(\square\)
Notation 4.2. This result is not true when \(n=2\).
Theorem 4.3. \(D^2(n)\) is Eulerian, if and only if \(n=5\).
Proof. \(D^2(n)\) is Eulerian if and only if it contains a cycle containing all the vertices of \(D^2(n)\). By Theorem 3.6, \(D^2(n)\) is a tree if and only if \(n\le4\). So we can assume that \(n\ge5\). Suppose \(D^2(n)\) is Eulerian and \(n>5\). By the above lemma, there exists a pair of vertices \((v,v+1)\) such that \(|deg_G(v)-deg_G(v+1)|=1.\) Therefore both degrees of the vertices \(v\) and \(v+1\) are not of the same parity and one of the vertices must have an odd degree. This contradicts the necessary and sufficient condition for an Eulerian graph that every vertex must be of even degree. Thus \(D^2(n)\) is not Eulerian for \(n>5.\)
Conversely if \(n=5\), then \(D^2(5)=C_5,\) which is Eulerian. \(\square\)
Result 4.4. \(D^2(n)\) is not Hamiltonian, if \(n\le4\).
For, \(n \le 4 \implies D^2(n)\equiv P_n\), which does not contain a Hamiltonian cycle.
Theorem 4.5. If \(n-1\) is a perfect square, then \(D^2(n)\) is Hamiltonian.
Proof. Let \(n-1\) be a perfect square.
We know that, for any n, there exists a Hamiltonian path \(1-2-3-….-(n-1)-n\) in the graph.
Also \((n-1)\) is a perfect square\(\implies n \ \text{and} \ 1 \ \text{are adjacent.}\) Hence we can easily find a Hamiltonian cycle \(1 – 2 – 3 – \dots – (n-1) – n – 1\). \(\square\)
Remark 4.6. The converse part of the above theorem is not true.
For example, Consider \(D^2(8)\) where the difference \(8-1=7\) is not a perfect square.
But \(D^2(8)\) is Hamiltonian, since there is a Hamiltonian cycle \(1 – 2 – 3 – 4 – 8 – 7 – 6 – 5 – 1\).
Theorem 4.7. \(D^2(n)\) is Hamiltonian if and only if \(n\in \mathbb{N}-\{1,2,3,4,6\}.\)
Proof. By Theorem 3.6, \(D^2(n)\) is a tree is \(n=1,2,3,4\) and hence not Hamiltonian. When \(n=5\), \(1 – 2 – 3 – 4 – 5 – 1\) is a Hamiltonian cycle.
Consider the graph of \(G=D^2(6).\) Take \(S=\{2,5\}.\)
Then \(\omega(G-S)\)= The number of components of \((G-S)=3\nleq|S|\).
Therefore \(D^2(6)\) is not Hamiltonian due to a well known necessary condition for Hamiltonian graphs [5]. So we can assume that \(n\ge7.\)
Case 1. If \(n \equiv 1 \pmod{4}\), let \(n=4t+1\) ; \(t \ge 2\).
Then \([1 – 2 – 6 – 10 – \dots – (4t-2)] – [(4t-1) – (4t-5) – \dots – 7 -3] -[4 -8 – \dots – (4t-4) – 4t] – [(4t+1) – (4t-3) – \dots – 9 – 5 – 1]\) is a Hamiltonian cycle.
For example, when \(n=21\), \([1 – 2 – 6 – 10 – 14 – 18] – [19 – 15 – 11 – 7 -3] -[4 -8 – 12 – 16 – 20] – [21 – 17 – 13 – 9 – 5 – 1]\) is a Hamiltonian cycle. When \(t=2, \ n=9, \text{then} [1-2-6] – [7-3] – [4-8] – [9-5-1]\) is a Hamiltonian cycle.
Case 2. If \(n \equiv 2 \pmod{4}\), let \(n=4t+2\) ; \(t \ge 2\).
Then \([1-2-3]- [4-8-12-\dots-4t] – [(4t-1)- (4t-5)-\dots-11-7)]-[6-10-14-\dots-(4t-2)- (4t+2)]- [(4t+1)- (4t-3)-\dots- 9-5-1]\) is a Hamiltonian cycle.
For example, when \(n=22\), \([1-2-3]- [4-8-12-16-20] – [19- 15-11-7]-[6-10-14-18-22]- [21- 17-13- 9-5-1]\) is a Hamiltonian cycle. When \(t=2, \ n=10, \text{then} [1-2-3] – [4-8] – [7] – [6-10] – [9-5-1]\) is a Hamiltonian cycle.
Case 3. If \(n \equiv 3 \pmod{4}\), let \(n=4t+3\) ; \(t \ge 1\).
Then \(1 – [2-6-10-\dots-(4t+2)]-[(4t+3)- (4t-1)-\dots-7-3]-[4-8-12-\dots- 4t]- [(4t+1)- (4t-3)- (4t-7)-\dots- 9-5-1]\) is a Hamiltonian cycle.
For example, when \(n=23\), \(1 – [2-6-10-14-18-22]-[23- 19-15-11-7-3]-[4-8-12-16- 20]- [21- 17- 13- 9-5-1]\) is a Hamiltonian cycle. When \(t=1, \ n=7, \text{then} [1] – [2-6] – [7-3] – [4] – [5-1]\) is a Hamiltonian cycle.
Case 4. If \(n \equiv 0 \pmod{4}\), let \(n=4t\) ; \(t\ge 2\).
Then \([1-2-3]- [4-8-12-\dots-4t]- [(4t-1)-(4t-5)-\dots-11-7]-[6-10-14-\dots-(4t-2)]- [(4t-3)-(4t-7)-\dots- 5-1]\) is a Hamiltonian cycle.
For example, when \(n=24\), \([1-2-3]- [4-8-12-16-20-24]- [23-19-15-11-7]-[6-10-14-18-22]- [21-17-13-9-5-1]\) is a Hamiltonian cycle. When \(t=2, \ n=8, \text{then} [1-2-3] – [4-8] – [7] – [6] – [5-1]\) is a Hamiltonian cycle. \(\square\)
Result 4.8. \(D^2(n)\) is connected, for all n.
For, the existence of an adjacency (u,v) between any two vertices of the form \((u,v=u+1)\) proves the existence of a path between any two vertices in \(D^2(n)\).
Hence, \(D^2(n)\) is connected.
Theorem 4.9. \(D^2(n)\) is planar, if and only if \(n\le 9\).
Proof. Consider \(D^2(10)\).
Let us form a subdivision of \(K_{3,3}\) using the vertices and edges of \(D^2(10)\). Let \(V(K_{3,3})=A \cup B\) where \(A=\{1,3,6\}\) and \(B=\{2,5,10\}\). The required nine connections are
i) using the edges \(1 – 2, 1 – 5, 1 – 10; 6 – 2, 6 – 5, 6 – 10\),
ii) using the internally disjoint paths \(3 – 2, 3 – 4 – 5, 3 – 7 – 8 – 9 – 10\).
Thus \(D^2(10)\) contains a subdivision of \(K_{3,3}\) and hence by Kuratowski’s theorem for planar graphs, \(D^2(10)\) is non-planar.
Also since, \(D^2(10)\) is an induced subgraph of all the graphs \(D^2(n)\) where \(n>10\), and \(D^2(10)\) is not planar, \(D^2(n)\) is not planar for \(n\ge10\).
Conversely, let \(n\le9\).
We need to prove that \(D^2(n)\) is planar. It is enough to prove the result for \(n=9\), since all the graphs \(D^2(n)\) for \(n\le8\) are subgraphs of \(D^2(9)\).
We consider the two disjoint cycles \(3 – 4 – 8 – 7 – 3\) and \(2 – 1 – 5 – 6 – 2\) of \(D^2(9)\). Join the spokes \(7 -6, 3- 2, 4 – 5.\) We have not yet used the vertex \(9\) and edges \(5 – 9\) and \(9 – 8\). Join \(5\) and \(8\) by the path \(5 – 9 – 8\). Thus it is possible to redraw the graph in the 2D-plane as shown below in such a way that its edges intersect only at the endpoints.
Thus \(D^2(n)\) is planar for \(n\ge9\).
\(\square\)
In this paper, we have attempted to form a new type of number theoretic graph called perfect difference graph. We have discussed most of the basic graph theoretic properties of \(D^2(n)\). For future work, one could consider the following problems.
i) Determine the Wiener index of \(D^2(n)\),
ii) Determine the chromatic number of \(D^2(n)\),
iii) Determine the various domination numbers of \(D^2(n)\).
We would like to thank Prof. M. Velrajan and Prof. R. Ramalakshmi for providing useful suggestions. We also would like to thank an anonymous referee for helpful comments to modify the proof of Theorems 2.4, 4.7 and 4.9.
Input: Upper limit lim
Output: The smallest integers a, b, and c such that:
\(a-1\) is a perfect square
\(b-1\) is a perfect square
\(b-a\) is a perfect square
\(c-1\) is a perfect square
\(c-a\) is a perfect square
\(c-b\) is a perfect square
Algorithm
Start.
Set the upper limit lim.
Initialize a variable Result as False.
For each value of \(a\) from \(2\) to \(\mathrm{lim}-1\):
Check whether \(a-1\) is a perfect square.
If not, continue to the next value of \(a\).
For each value of \(b\) from \(a+1\) to \(\mathrm{lim}-1\):
Check whether both \(b-1\) and \(b-a\) are perfect squares.
If either condition fails, continue to the next value of \(b\).
For each value of \(c\) from \(b+1\) to \(\mathrm{lim}-1\):
Check whether \(c-1\), \(c-a\), and \(c-b\) are all perfect squares.
If all conditions are satisfied:
Display the values of \(a\), \(b\), and \(c\).
Display the smallest value of \(c\).
Set Result \(=\) True.
Exit all loops.
If Result is still False after completing the loops, display “No solution found up to lim”.
Stop.
Auxiliary Function: is_square(n)
If \(n<0\), return False.
Compute the integer square root \(r=\operatorname{isqrt}(n)\).
If \(r\times r == n\), return True; otherwise, return False.
Program Coding:
import math
def is_square(n):
if n < 0:
return False
r = math.isqrt(n)
return r * r == n
lim = 585810
Result = False
for a in range(2, lim):
if not is_square(a - 1):
continue
for b in range(a + 1, lim):
if not is_square(b - 1) or not is_square(b - a): continue
for c in range(b + 1, lim):
if (is_square(c - 1) and
is_square(c - b) and
is_square(c - a)):
print(f"Result: a={a}, b={b}, c={c}")
print(f"Smallest c = {c}")
Result = True
break
if Result:
break
if Result:
break
if not Result:
print("No solution found up to", lim)Output:
Result: a=23410, b=34226, c=485810
Smallest c = 485810