---

The Mobius function in [11, 8] , is a well known function in Number theory and it is defined by µ(1)=1 and if n>1, we write n=p₁^a1p₂^a2p₃^{a 3}....p_k^ak, then,

The graph G in [3, 6], is a triple G (V, E, ψ), consisting of a finite set V of elements called vertices with a set E of unordered pair of elements of V called the edges and ψ is the incident relation between vertices and edges. Two vertices u and v are adjacent, if there is an edge e incident with the vertices u and v. The number of edges incident with a vertex u is called the degree of u and it is denoted by d(u). The minimum and maximum degrees of a vertex of a graph are respectively denoted by δ and Δ.

Here we consider the graph, G (V, E) by defining on the powerful arithmetic function called Mobius function. The graph of Mobius function for '0' is denoted by G(µ_n⁽⁰⁾). Its vertex set is the set of first n natural numbers and the two vertices a, b are adjacent if and only if µ(ab)=0. The Graph theory is closely related to many other branches of Mathematics namely Group theory, Ring theory, Number theory, Topology, etc. In particular, Chalapathi and Madhavi [5] used the symmetry of Group theory in the arithmetic Cayley graph, Anderson and Badawi [1], Eswara Rao and Bharathi [7] [2] worked on the graphs with vertex set as a commutative ring. The use of number theory in the graph theory was first introduced by Nathanson [10]. He used the congruence of two numbers to define the adjacency between two vertices. In 1971, Cadogan [4] used the Mobius function for the calculation of coefficients in the counting series for unlabelled connected graphs. In [12], Vasumathi introduced a new class of graph called Mobius graph. The vertex set of this graph is the first n natural numbers and two vertices of this graph are adjacent if and only if µ(ab)=0. The graphs considered in this paper are all simple graphs.

Vasumathi [12] gives the degree of each vertex of G(µ_n⁽⁰⁾) as the following lemma.

1.1 Lemma 1

If u (u ≠ 1) is any vertex in G(µ_n⁽⁰⁾) then,

and if u=1, then,

Using the above lemma, the authors discussed the minimum degree and maximum degree of the graph.

Theorem 1:

The minimum degree of the graph,

Proof:

Let G(µ_n⁽⁰⁾) be a graph with n vertices.

From the Lemma 1, the degree of the vertex 1 is given by,

Let u be any vertex of G(µ_n⁽⁰⁾) such that µ(u)=1, u≠1

Then the vertex u is adjacent to every vertex x such that µ(x) =0, since µ(u.x)=0

Also the vertex u may be adjacent to other vertex y such that µ (y)≠ 0, (u,y)≠1,where y≤n

So, the neighborhood of the vertex u is N(u)= {x/µ(x) =0} U {y/µ(y)≠0, (u,y) ≠ 1}

Thus,

Then, d(u)≥d(1)

Similarly, for any vertex w of G(µ_n⁽⁰⁾) such that µ(w)=-1

Then the vertex w is adjacent to every vertex x such that µ(x)=0, since µ(w.x)=0

Also the vertex w may be adjacent to other vertex y such that µ (y)≠0, (w,y)≠1, where, y≤n

So, the neighborhood of the vertex w is N(w)= {x/µ(x)=0} U {y/µ(y)≠ 0, (w,y)≠1}

Thus,

Implies that d(w) ≥ d(1)

Now it is clear that, the degree of the vertex z is d(z) = n-1 such that µ(z) = 0

Thus the degree of the vertex 1 is the minimum degree of the graph G (µ_n⁽⁰⁾)

Hence the minimum degree of the graph,

Theorem 2:

The maximum degree of the graph G(µ_n⁽⁰⁾) is Δ=n-1

Proof:

Let G(µ_n⁽⁰⁾) be a graph with n vertices

Let u be any vertex such that µ(u)=0

Also let v be any another vertex.

Now, µ(uv)=0

Therefore, u,v are adjacent vertices.

Since, v is an arbitrary vertex, then, u is adjacent to all the remaining vertices.

Since the graph has n vertices and it is a simple graph.

Then, u is adjacent to n-1 vertices.

i.e., d(u) = n-1

Let w be a vertex such that µ(w)≠0

then we have µ(w)=1 or µ(w)=-1

Implies,µ(1,w)=µ(w)=1 or -1≠0

Therefore, w is not adjacent to the vertex 1

And w is adjacent to not more than n-2 vertices.

i.e., d(w)≤n-1

Therefore, the vertex u such that µ(u)=0 has the degree n-1, which is the maximum of the degrees of all the vertices.

Therefore, the maximum degree of the graph, G (µ_n⁽⁰⁾) is Δ=n-1.

The graph G(µ₄⁽⁰⁾) has the minimum degree,δ=1, which is the degree of the vertex 1 and the maximum degree, Δ=4-1=3, which is the degree of the vertex 4 shown in the Figure 1.

Now, the following theorems describe the adjacency of two vertices based on the divisibility of two vertices.

Theorem 3:

In the graph G(µ_n⁽⁰⁾), every pair of distinct prime vertices are not adjacent.

Proof:

Let G(µ_n⁽⁰⁾) be a graph

Let p, q be prime vertices in the set of vertices of G (µ_n⁽⁰⁾) and 1≤ p, q ≤ n, p≠ q

Since p=p¹ and q=q¹

Let k=pq

Implies, k=p¹q¹ and p≠q

Implies, µ(k)= (-1)² = 1

Therefore,µ(pq)=1≠0

Therefore, the vertices p,q in G(µ_n⁽⁰⁾)are not adjacent.

Hence, every pair of distinct prime vertices are not adjacent in G (µ_n⁽⁰⁾)

The graph G(µ₁₃⁽⁰⁾) has the vertices 7, 11, 13 which are distinct primes and there are no edges between them, so that they are not adjacent to each other. It is shown in Figure 2.

Theorem 4:

If gcd(k,l)≠1 for 1≤ k,l≤n, then k,l are adjacent in G (µ_n⁽⁰⁾). But, the converse need not be true.

Proof:

Let k,l are two vertices in the graph G(µ_n⁽⁰⁾ ), 1≤k, 1≤n

If gcd(k,l)≠1

Then, gcd(k,l)>1

We have, k = p₁^α1 p₂^α2 ....p₃^α3 , p_i's are primes

l = q₁^β1 q₂^β2 ....q₃^β3 , q_j's are primes.

Since, gcd (k,l)≠ 1,

Implies, p_i = q_j for some i,j

Now,

Clearly, α_i + β_j > 1 and p_i’s, q_j’s are all primes.

Implies, µ(kl)=0

Therefore, k,l are adjacent in G(µ_n⁽⁰⁾)

The converse need not be true.

Because, in the graph G(µ_n⁽⁰⁾), n≥5,

The vertices 4 and 5 are adjacent but gcd (4, 5) =1

Hence, if gcd (k,l)≠ 1, then k,l are adjacent in G (µ_n⁽⁰⁾) but not the converse.

Corollary of Theorem 4:

For 1 < k,l ≤ n, if k/l or l/k, then k,l are adjacent in G (µ_n⁽⁰⁾)

Proof:

Let G(µ_n⁽⁰⁾) be a graph of Mobius function for 0.

For 1 < k, l ≤ n,

Let k/l or l/k.

If k/l, then gcd(k,l) = k > 1.

Implies, gcd(k,l) ≠ 1 and from Theorem 4,k,l are adjacent in G (µ_n⁽⁰⁾)

If l/k, then gcd(k,l) = l > 1

Implies, gcd(k,l)≠ 1 and from Theorem 4,k,l are adjacent in G (µ_n⁽⁰⁾)

The graph G(µ₂₀⁽⁰⁾) has the vertices 6 and 10 such that gcd (6,10) = 2 ≠ 1 and these vertices 6, 10 are adjacent. Also, 5 and 15 are vertices such that 5/15 and these vertices 5, 15 are adjacent. It is shown in Figure 3.

Theorem 5:

In a graph G(µ_n⁽⁰⁾), for 1≤ k < k + 1 ≤ n, k, k + 1 are adjacent vertices if and only if either µ (k) =0 or µ (k+1) = 0.

Proof:

Let us consider the graph G(µ_n⁽⁰⁾) with n vertices.

Let us suppose k, k + 1 are adjacent vertices, where, 1≤ k < k + 1≤ n.

Then we have,

Also,

Implies, k.k + 1 = p₁^α1 p₂^α2 ....p_r^αr .q₁^β1 q₂^β2 ....q₃^β3

Since, k, k+1 are adjacent vertices in G(µ_n⁽⁰⁾ ) then µ(k.k+1)=0

Then k.k + 1 = p₁^α1 p₂^α2 ....p_r^αr .q₁^β1 q₂^β2 ....q₃^β3 has at least one α_i or β_j is greater than 1.

Then there exists α_x or β_y such that, α_x > 1 and β_y > 1, where 1≤ x ≤ r, 1 ≤ y ≤ s.

If α_x > 1, then µ(k) = 0, where 1 ≤ x ≤ r.

If β_y > 1, then µ(k+1) = 0, where 1 ≤ y ≤ s.

That is if µ (k.k+1) = 0, then µ(k) = 0 or µ (k+1) =0

Thus, if k,k+1 are adjacent in G(µ_n⁽⁰⁾), then either µ(k) = 0 or µ (k+1) =0, where 1≤k< k +1 ≤ n

Conversely, let us suppose that either µ(k) =0 or µ (k+ 1) = 0, for 1≤ k < k + 1 ≤ n

If µ(k) = 0, then in equation (1), at least one α_i is greater than 1, 1 ≤ i ≤ r

then, k.k + 1 = p₁^α1 p₂^α2 ....p_r^αr .q₁^β1 q₂^β2 ....q₃^β3 where at least one α_i is greater than 1.

Implies, µ(k.k+1) = 0

Similarly, from equation (2), if µ(k+1) = 0, then µ(k.k +1)=0

That is if either µ(k) = 0 or µ(k+1) = 0, for 1 ≤ k < k + 1 ≤ n, then µ (k.k+1) = 0

So that k, k+1 are adjacent in G(µ_n⁽⁰⁾)

Hence, in a graph G(µ_n⁽⁰⁾), for 1 ≤ k < k + 1 ≤ n, k, k +1 are adjacent vertices if and only if either µ (k) = 0 or µ (k + 1) = 0.

From Figure 3, we can observe that the vertices k=7, k+1=8 are adjacent in G(µ₂₀⁽⁰⁾) and µ(k+1) = 0. Also, the vertices k=12,  k+1=13 such that µ(k) = 0 and k,k+1 are adjacent.

Theorem 6:

If n ≥ 9, then the graph G(µ_n⁽⁰⁾) is non-planar.

Proof:

Consider the graph of Mobius function for '0' with n vertices, G (µ_n⁽⁰⁾)

Let us assume that n≥9.

Then the graph has the vertices 3, 4, 6, 8, 9.

Since,µ(4)=µ(8)=µ(9)=0, then the vertices 4, 8, 9 are adjacent to all other vertices in the graph G (µ_n⁽⁰⁾),n ≥9.

And since, µ(3.6) = 0, then the vertices 3, 6 are also adjacent to each other.

Thus there forms a complete sub graph with the vertices 3, 4, 6, 8, 9 of the graph G(µ_n⁽⁰⁾), n ≥ 9 which is shown in Figure 4 and it is the Kuratowski's first graph.

By the Kuratowski theorem in [9],

The graph G(µ_n⁽⁰⁾), n≥ 9 is a non- planar graph.

Remark:

By observing the graphs G(µ_n⁽⁰⁾), n ≤ 8, it is clear that these graphs are planar graphs. For example, Figure 5 shows that the graph G(µ₈⁽⁰⁾) is a planar graph.

In this paper, the authors have defined a graph of Mobius function for '0' and have discussed some basic results. This paper is an opening for making another bridge between graph theory and number theory. Here the authors have calculated the minimum degree of this graph by using the value of degree of each vertex and it is found that the degree of the vertex is 1. Next the maximum degree of the vertex is calculated as n-1, where n is the number of vertices of the graph of Mobius function for '0'. Also, proved the sufficient condition for adjacency as, (i) if two vertices are distinct primes then they are not adjacent and (ii) if the greatest common divisor of two vertices is more than 1, then they are adjacent but not the converse. And established the necessary and sufficient condition for two consecutive vertices are adjacent is that, at least one of them has the Mobius function value of '0'. Finally, it is proved that, if the number of vertices are more than 8, then the graph is not a planar graph.