Abstract

A is a labelled graph denoted by in which the vertex set of an has vertices labeled {} and edges such that there exist an edge between two distinct vertices labeled { and }, if { and } are coprime to each other. In this paper, some properties of the ER- are studied. An algorithm to compute GCD and LCM of any two numbers between and p by means of an ER- graph is also described.

AMS Subject Classification 2000: 11A41, 05C12, 05C07.

1. Introduction

In number theory, the totient function or Euler's phi function of a positive integer plays a vital role in group theory ¹. It determines the size of the multiplicative group modulo . Apart from this, it also finds application in one of the very prevalent cryptographic techniques called RSA algorithm. It is well known that, is defined as the number of integers less than or equal to , that are coprime to . Paul Erdös extensively worked on co-prime graphs ². He has established very good fundamental results on number of cycles in coprime graphs. Further in ³, the author has studied exclusively on graph labeling and Euler's Phi function for planar graphs. Motivated by this, we study the co-prime graphs from spectral theory perspective. In this paper we apply graph theoretic approach to study the based on coprime graph labelling. More graph labelling techniques can be found in ⁴. The coprime labeled graph is denoted by ER-. The vertex set of ER- has vertices, labeled with {} and edges. If two distinct vertices labeled and are coprime, then there exists an edge between them.

This paper is organized into four sections. In section 2, main results are discussed. In section 3, algorithms to compute the greatest common divisor (GCD) and the least common multiplier (LCM) of any two given numbers between 1 and using ER- are described. Final section is for conclusions. For terminology and notations, one can look at ^{1, 5}. The following are the most used notations:

(1) is the set of prime numbers up to a real number x.

(2) is the GCD of two numbers a and b and is the LCM of them.

(3) A wheel graph is a graph with p vertices, formed by connecting a single vertex to all vertices of a cycle.

(4) Chromatic number of a graph G is the minimum number of colors to properly color the graph.

(5) Chromatic polynomial of a graph is the number of different ways of properly coloring a labeled graph by colors.

(6) Dominating set of a graph is a subset of such that every vertex of is adjacent to some vertex of .

(7) Domination Number is the cardinality of the smallest dominating set.

(8) is the line graph of .

(9) Permanent of a matrix is the sum , where runs over all permutations of the set

(10) Energy of a graph is the sum of the absolute eigenvalues of the adjacency matrix of that is, , where are the eigenvalues of ⁶.

(11) Two graphs are said to be equi-energetic if and only if their energies are equal ⁷.

(12) - is a variant of ER in which the vertices of the graph are labeled with the first prime numbers and .

2. Results

In this section, we state some observations and results of an ER- graph.

(1) ER is a simple connected graph without pendant vertex.

(2) - .

(3) The trivial graph is an graph.

(4) and are the only complete graphs which are graphs.

(5) For , the ER- is not a regular graph.

(6) ER- has a star graph as its subgraph.

(7) For the ER-,

(i) The girth is 3.

(ii) The circumference is p.

(iii) The diameter is 2.

Theorem 2.1. The number of edges in ER- is

Proof. By definition of an graph, there exists an edge between any two distinct vertices and of the ER- if and only if and . Thus, the vertex labelled with has number of edges with vertices in . Similarly the vertex labelled with has edges with vertices in {}, excluding the edge with vertex if any, since this edge is already counted within the edge set of vertex labeled by . Continuing this way for any arbitrary vertex labelled by , there are edges with vertices in excluding the edges with vertices from if any, as these edges are already accounted with the edge set of vertices of . Similarly the vertex labelled by 2 is having one edge with vertex labelled by 1 with excluding those edges which are associated with and finally vertex labeled by 1 has zero edges with excluding those edges which are associated with . Thus the total number of edges in ER- is .

Corollary 2.2. The number of edges in ER- is less than or equal to .

Proof. From Theorem 2.1,

and using the Euler's totient property, , we get

Thus

Example 1. The number of edges in ER- is The number of edges in ER- is , where is the number of edges in ER-.

Theorem 2.3. If and is odd, then ER- contains a spanning sub-graph as a wheel graph .

Proof. The proof can be given in two steps: 1) The ER- has cycles, and 2) Every vertex of has an edge with a distinguished vertex. Without loss of generality, let the vertex labelled by 1 be the distinguished vertex and the vertices be the possible vertices of . Since every vertex labelled by is coprime with the vertices labelled and . By the virtue of this, it has an edge with the vertices labeled by and and since is odd, the vertex labelled by 2 has an edge with vertex labelled by and 3. Thus these edges together with the vertices form a cycle . By definition, every natural number is co-prime to 1. Thus all the vertices labelled by of has an edge with the vertex labelled by 1. Hence ER- contains a wheel spanning subgraph .

Corollary 2.4. If and is even, then ER- contains a subgraph .

Proof. Using Theorem 2.2, as is even, there can't be an edge between the vertices labelled by 2 and . Thus no cycle can be formed with the vertices . Thus an ER- contains a subgraph , whenever is even.

Theorem 2.5. ER- is also an ER- graph and is isomorphic to ER-.

Proof. ER- is a graph obtained by removing the vertex labelled by and all the edges associated with it. Thus the resultant graph has vertices and there exist an edge between any pair of vertices if and only if their labels are co-primes. Hence ER- is ER- graph having number of vertices and edges as and , respectively, and therefore, is isomorphic to ER graph.

Theorem 2.6. If is the set of primes up to , then maximal clique in ER- is .

Proof. Since any two prime numbers are coprime, there exist edges between all the vertices labelled with prime numbers, and as these numbers are coprime with 1, they together form a complete graph with vertices. Thus the maximal clique in ER- is .

Corollary 2.7. The chromatic number of ER- is .

Proof. By using Theorem 2.5, maximal clique in ER- is . Hence it requires colors to color the prime labelled vertices and one more color to color the vertex labelled by . Since the remaining vertices can be colored by colors. Thus -) is .

Theorem 2.8. Let be the set of prime numbers from 1 to with and Then chromatic polynomial of ER- is given by

Proof. Let there are colors available to color graph ER- By corollary 2.7, for . Wlog, let and we color the vertices labled with , in ways respectively.

Let be the set of sets with the following properties.

Let ={vertex labeled with 1}. Let be the set of vertices which are labeled with the numbers which are divisible by prime . Then .

Let be the set of vertices which are labeled with the numbers which are divisible by prime and not divisible by prime . Then .

Wlog, for all in , let be the set of vertices which are labeled with the numbers which are divisible by prime and not divisible by primes , , , ... . Then

Further vertex of set can be colored in ways and for in , all the vertices of the set are not connected to each other and hence all the vertices of this set can be colred with the same color and thus every vertex of this set can be colored in ways. Thus in total all the vertices of can be clored in or ways.

Theorem 2.9. If pi is a prime number which is a label of a vertex v in ER- then the degree of v is

Proof. Let a vertex in ER- be labelled by a prime number , where . The maximum degree of any vertex in ER is . Then number of non-coprimes from 1 to with is . Since is a prime number and no number except 1 and itself can divide . Thus number of coprimes from 1 to with is . By the definition of ER, the degree of this vertex is

Theorem 2.10. The sum of degrees of vertices labelled with non prime vertices in is

(1)

where and each is a prime number.

Proof. Let the vertices and are labelled with non-prime and prime numbers respectively. Also let be the set of numbers such that . It is well-known that the sum of degrees of all the vertices of any graph is twice the number of edges in it. By using this and Theorems 2.1 and 2.8,

i.e.,

i.e.,

This completes the proof.

Theorem 2.11. If then ER- always contains a Hamiltonian cycle.

Proof. Case 1: Let be odd. By using mathematical Induction: it is true for the ER is , since is a Hamiltonian graph. Now assume that it is true for . We want to prove it for . By definition and Theorem 2.2, ER has a spanning subgraph as wheel graph . But a wheel graph has a Hamiltonian cycle. Thus ER has a Hamiltonian cycle.

Case 2: Let be even and is the vertex set labeled with . By Corollary 2.3, ER contains a spanning subgraph then there exist a path and edge or path () between the vertices (labeled 1) and (labeled ). By joining these two paths, a cycle is formed, which proves the theorem for even also. Hence the result is true all values of . Note that (L(ER-) is also a Hamiltonian graph).

Theorem 2.12. The domination number and the total domination number of ER- is --.

Proof. In ER-, the vertex labeled by 1 is adjacent to all the other vertices. Thus the set {1} is the minimum dominating set of $ER$- having the cardinality 1. Thus -. Similarly - .

Theorem 2.13. If ER is non-planar.

Proof. By Kuratowaski's theorem on planarity, a graph is non-planar if and only if it contains either or as its subgraph, or obtains any of these subgraphs by means of homeomorphic operations. By Theorem 2.5, every ER has as its maximal clique. For , the number of primes is Thus ER has Kuratowaski's 2nd graph as its subgraph. Thus ER is non-planar.

Remark 2.14. With , no Kuratowaski's graph exists as a subgraph in ER and also these graphs can be embedded in a plane surface. Hence they are planar graphs.

Theorem 2.15. If , , then ER- has wheel subgraphs ,. Therefore, the number of wheel subgraphs is .

Proof. By Theorem 2.4, it is true that, ER has ER as its subgraph and is also an graph. Since is odd, by Theorem 2.2, this graph has as its spanning subgraph. But the fact that is even implies ER- has no wheel subgraphs . But is odd and ER is also an graph and has as its subgraph. Thus alternating graphs have wheel subgraphs when the number of vertices is odd. Finally this process is continued till the number of vertices of reaches 5, which has as its subgraph. Thus ER has wheel subgraphs .

Theorem 2.16. The graph - is .

Proof. By the definition, vertices of this graph are labelled by prime numbers and one vertex labeled as 1. All these labels are coprime to each other and hence there exist an edge between every pair of vertices. Thus - is .

Theorem 2.17. The number of edges in ER is if is prime, and if is composite, where is the number of edges in an ER- graph.

Proof. By construction method. Consider an - graph. Let be the vertex labeled by of the trivial graph . Now the graph ER- is constructed from ER- and by the following procedure. If is prime, then is coprime to all the numbers . ER- Then . If is composite, then is coprime to numbers among Then ER- is constructed by adding edges between the vertices of ER- and the vertex labeled of , such that the labels of the vertices of ER- are coprime with the vertex labeled of . Thus .

3. Eigenvalues of an ER- φ(G(p, q)) Graph

The adjacency matrix of - is defined by its entries if and 0 otherwise. Since is symmetric, its eigenvalues are real. Without loss of generality, we can write them as and call them the eigenvalues of .

Lemma 3.1. ⁸ Let be a graph with sub-vertex set having same set of neighbors , where Then this graph has at least equal eigenvalues 0. Also the corresponding eigenvectors are

Theorem 3.2. Let ER be a graph of order . Also let be a prime number with positive integer such that , . Then one of the eigenvalues of the adjacency matrix of an ER- graph is of multiplicity .

Proof. Since is an prime number, vertices with label have same set of neighbors. By Lemma 3.1, we conclude that ER- graph has at least equal eigenvalues 0, . This completes the proof.

Theorem 3.3. If is a prime number, then one of the eigenvalues of the adjacency matrix of an ER- graph is .

Proof. Since is a prime, there exist at-least two vertices labeled 1 and having degree . Then the adjacency matrix ( matrix) of the graph is given by

Now,

by applying the transform

by the determinant property.

To compute the eigenvalues of , write

From above, we get , that is, . Hence -1 is one of the eigenvalues of ER.

Remark 3.4. From the proof of Theorem 3.3, we conclude that if there are vertices of ER having degree then the multiplicity of eigenvalue -1 of ER is .

In mathematics, Bertrand's postulate (actually a theorem) was proven by several researchers (see, ⁹). Using Bertrand's postulate, we prove the following result:

Theorem 3.5. One of the eigenvalues of the adjacency matrix of ER- graph is .

Proof. If is prime, then the proof is same as Theorem 3.3. Otherwise, is composite. Then the proof is based on prime gaps. A prime gap is the difference between two successive prime numbers. To prove this theorem, the Bertrand's postulates ^{10, 11, 12} are applied. It states that there is always a prime number between and 2x. Any vertex in ER- has degree if it is labelled by 1 or a prime number such that = 1 for every such that is not a divisor of the numbers from to . By Bertrand's postulates, there is always a prime number between and as is composite. Without loss of generality, let be the nearest prime, which is less than and . Now is the least number divisible by . Since , then is not a divisor of numbers between to . Hence the degree of the vertex that is labelled by is . Thus there exist at least two vertices labeled by 1 and having degree . By applying Theorem 3.3 and Bertrand's postulates result is proven.

Let and be two graphs with and vertices, and and edges, respectively. The union of two graphs and , written , is the graph with vertex set and edge set . The join of graphs and with disjoint vertex sets and , and edge sets and is the graph union together with all the edges joining and . Thus, for example, \,, the complete bipartite graph.

Theorem 3.6. One of the eigenvalues of the adjacency matrix of graph is zero and its multiplicity is at least for .

Proof. Let - By Theorems 3.3 and 3.5, there exist at least two vertices having degree in an , where is the number of vertices and is the number of edges in . Then we have

where is a graph of order with edges. Thus we have

Let be the characteristic polynomial of graph . From above one can see easily that

This completes the theorem.

The energy of the graph G is defined as

This quantity has a long known chemical application; for details see the surveys ^{13, 14, 15}. Recently much work on graph energy appeared also in the mathematical literature (see, for instance, ^{16, 17, 18, 19}).

Theorem 3.7. If is prime, then are equi-energetic graphs.

Proof. Denote by and .

Let , and , be the energies and adjacency matrices of two graphs and , respectively. Since is a prime and is co-prime with all numbers , this implies that in , the vertex labeled by has edges with all the vertices of . Thus we have

Let the eigenvalues of be . From above one can see easily that the eigenvalues of are and 0. Therefore . Hence the result follows.

Theorem 3.8. Permanent of adjacency matrix of is zero.

Let be the adjacency matrix of . Since the vertex labeled by 1 is adjacent to allthe vertices of the graph ER- and , it is not adjacent to none of the vertices of. By Theorems 3.3 and 3.5, this implies that has at least two rows with allzeros. Without loss of generality, let the 1st and th rows bezero rows. Using the definition of the permanent of matrix we get = = , where is a permutation over . In each of the products of sums, there exists at least one term which has elements of the and rows. Thus all the products of sums vanishes to zero. Hence the permanent of adjacency matrix is zero.

Theorem 3.9. The number of edges of a line graph of is

where is labelled with non-primes.

Proof. The number of edges of a $line$ $graph$ of is given by , where is the degree of the vertex of . By Theorem 2.1, for an , . The vertices of the graph can be partitioned into 3 sets: vertices labeled with prime numbers, vertices labeled with composite numbers and vertex labeled with 1 and their cardinalities are and 1, respectively. By using Theorems 2.1 and 2.3, the theorem is proved.

Let be the diagonal matrix of vertex degrees of graph Then the Laplacian matrix of is , where is the adjacency matrix of Let denote the eigenvalues of . They are usually called the Laplacian eigenvalues of . Among all eigenvalues of the Laplacian of a graph, the most studied is the second smallest, called the algebraic connectivity of a graph. It is well known that a graph is connected if and only if . Besides the algebraic connectivity, is the invariant that interested the graph theorists. The following two results are obtained in ²⁰ and ²¹.

Lemma 3.10. ²⁰ Let be a graph with Laplacian spectrum . Then the Laplacian spectrum of is }, where is the complement of the graph .

Lemma 3.11. ²¹ Let be a graph with vertex subset having the same set of neighbors , where . Then this graph has at least equal eigenvalues and they are all equal to the cardinality of the neighbor set. Also the corresponding eigenvectors are

Theorem 3.12. Let ER- be a graph of order . Also let be a prime number with positive integer such that , . Then the eigenvalues of the Laplacian matrix of an ER- graph is of multiplicity Moreover, the largest two Laplacian eigenvalues are .

Proof. Since is an prime number, vertices with label have same set of neighbors. By Lemma 3.11 and Theorem 2.9, we conclude that ER- graph has at least equal eigenvalues ,

We have that two adjacent vertices are adjacent to all the remaining vertices of the graph ER- by the proofs of Theorems 3.3 and 3.5. This implies that graph ER- has at least two vertices of degree , that is, graph has two isolated vertices. By Lemma 3.10, we conclude that the largest two Laplacian eigenvalues are . This completes the proof.

4. An Algorithm to Compute GCD and LCD of Two Numbers.

Though the is constructed using GCD concept, from its adjacency matrix, the GCD and LCM of any two numbers from 1 to can be computed with less complexity and this can easily be extended to higher order of the graphs. This is one of the techniques for finding GCD and LCM. The algorithm to compute the GCD of two numbers is as follows:

(1) Determine the adjacency matrix A of

(2) If A(a, b) = 1 or a = b, then (a,b) = 1.

(3) If then (a, b) = a or (if , then (a, b) = b); else find the common non neighbors of i and j, excluding 1.

(4) MinCommonNeighbour = minimum(common non-neighbors of i and j.)

(5) (a; b) = minimum(a, b; minCommonNeighbour)

(1) Determine the adjacency matrix A of

(2) If

(3) If or , then .

(4) Compute (a, b) using algorithm 3.1.

(5)

5. Conclusion

In this paper, we studied the spectral properties of co-prime labeled graphs () based on Euler's function. Several properties including connectivity, coloring and domination of these graphs are stated and proved. As part of further research, the study of generic spectral properties of these graphs is in progress.

Acknowledgements

K. C. Das was partially supported by the Faculty research Fund, Sungkyunkwan University, 2012 and Sungkyunkwan University BK21 Project, BK21 Math Modeling HRD Div. Sungkyunkwan University, Suwon, Republic of Korea.

References