Odd mean labeling for two star graph

All graphs in this paper are finite, simple and undirected. Terms not defined here are used in the sense of Harary [1]. In 1966, Rosa [3] introduced β−valuation of a graph. Golomb subsequently called such a labeling graceful. In 2015, Maheswari and Ramesh [2] proved the two star graph G = K_1,m ∧ K_1,n is a mean graph if and only if |m − n| ≤ 4. We prove the two star graph G = K_1,m ∧ K_1,n is an odd mean graph if and only if |m − n| ≤ 3.

The corresponding edge labels are as follows: The edge label of uu_i is 2i − 1 for 1 ≤ i ≤ m. The edge label of vv_j is q + 2j for 1 ≤ j ≤ n − 1. The edge label of vv_n is 2q − 1. Also, the wedge u₁v_n is 2m + 1. Therefore, the induced edge labels of G = {1,3,5,...,2m − 1,2m + 3,...,4m + 1} and has 2m + 1 distinct edges.

Hence the vertex labels and the induced edge labels of G are distinct.

Thus G = K_1,m ∧ K_1,n is an odd mean graph when n = m.

Case:2n = m + 1.

Consider the graph G = K_1,m ∧ K_1,n. Let {u} ∪ {u_i : 1 ≤ i ≤ m} and {v} ∪ {v_j : 1 ≤ j ≤ m + 1} be the vertex set of K_1,m and K_1,n respectively. Then G = K_1,m ∧ K_1,n has 2m + 3 vertices and 2m + 2 edges.

The required vertex labeling f : V (G) → {0,1,2, ⋅⋅⋅, 2q − 1} is defined as follows,

f(u)=0;f(ui)=4i−3f(vj)=4jf(vn)=2q−1.forforf(v)=2q−2;1≤i≤m;1≤j≤n−1;$$\begin{array}{} \displaystyle \begin{array}{*{20}{c}} {\begin{array}{*{20}{c}} {f(u) = 0;} \hfill \\ {f({u_i}) = 4i - 3} \hfill \\ {f({v_j}) = 4j} \hfill \\ {f({v_n}) = 2q - 1.} \hfill \\ \end{array}} & {\begin{array}{*{20}{c}} {{\rm{for}}} \\ {{\rm{for}}} \\ \end{array}} & {\begin{array}{*{20}{c}} {f(v) = 2q - 2;} \hfill \\ {1 \le i \le m;} \hfill \\ {1 \le j \le n - 1;} \hfill \\ {} \hfill \\ \end{array}} \\ \end{array} \end{array}$$

The corresponding edge labels are as follows: The edge label of uu_i is 2i − 1 for 1 ≤ i ≤ m. The edge label of vv_j is q + 2 j − 1 for 1 ≤ j ≤ n − 1. The edge label of vv_n is 2q − 1. Also, the wedge u₁v_n−1 is 2m + 1. Therefore, the induced edge labels of G = {1,3,5,...,2m − 1,2m + 3,...,4m + 3} and has 2m + 2 distinct edges.

Hence the vertex labels and the induced edge labels of G are distinct.

Thus G = K_1,m ∧ K_1,n is an odd mean graph when n = m + 1.

Case:3n = m + 2.

Consider the graph G = K_1,m ∧ K_1,n. Let {u} ∪ {u_i : 1 ≤ i ≤ m} and {v} ∪ {v_j : 1 ≤ j ≤ m + 2} be the vertex set of K_1,m and K_1,n respectively. Then G = K_1,m ∧ K_1,n has 2m + 4 vertices and 2m + 3 edges.

The required vertex labeling f : V (G) → {0,1,2, ⋅⋅⋅, 2q − 1} is defined as follows,

f(u)=2;f(v)=2q−2;f(u1)=0;f(ui)=4i−5for2≤i≤m;f(vj)=4j−3for1≤j≤n.$$\begin{array}{} \displaystyle \begin{array}{*{20}{c}} {f(u) = 2;} \hfill & {} \hfill & {f(v) = 2q - 2;} \hfill \\ {f({u_1}) = 0;} \hfill & {} \hfill & {} \hfill \\ {f({u_i}) = 4i - 5} \hfill & {{\rm{for}}} \hfill & {2 \le i \le m;} \hfill \\ {f({v_j}) = 4j - 3} \hfill & {{\rm{for}}} \hfill & {1 \le j \le n.} \hfill \\ \end{array} \end{array}$$

The corresponding edge labels are as follows: The edge label of uu₁ is1. uu_i is 2i − 1 for 2 ≤ i ≤ m. The edge label of vv_j is q + 2 j − 2 for 1 ≤ j ≤ n. Also, the wedge u₁v_n−1 is 2m + 1. Therefore, the induced edge labels of G = {1,3,5,...,2m + 1,2m + 3,...,4m + 5} and has 2m + 3 distinct edges.

Hence the vertex labels and the induced edge labels of G are distinct.

Thus G = K_1,m ∧ K_1,n is an odd mean graph when n = m + 2.

Case:4n = m + 3.

Consider the graph G = K_1,m ∧ K_1,n. Let {u} ∪ {u_i : 1 ≤ i ≤ m} and {v} ∪ {v_j : 1 ≤ j ≤ m + 3} be the vertex set of K_1,m and K_1,n respectively. Then G = K_1,m ∧ K_1,n has 2m + 5 vertices and 2m + 4 edges.

The required vertex labeling f : V (G) → {0,1,2, ⋅⋅⋅, 2q − 1} is defined as follows,

f(u)=1;f(v)=2q−2;f(v1)=0;f(ui)=4i+1for2≤i≤m;f(vj)=4j−5for2≤j≤n.$$\begin{array}{} \displaystyle \begin{array}{*{20}{c}} {f(u) = 1;} \hfill & {} \hfill & {f(v) = 2q - 2;} \hfill \\ {f({v_1}) = 0;} \hfill & {} \hfill & {} \hfill \\ {f({u_i}) = 4i + 1} \hfill & {{\rm{for}}} \hfill & {2 \le i \le m;} \hfill \\ {f({v_j}) = 4j - 5} \hfill & {{\rm{for}}} \hfill & {2 \le j \le n.} \hfill \\ \end{array} \end{array}$$

The corresponding edge labels are as follows: The edge label of uu_i is 2i + 1 for 1 ≤ i ≤ m. The edge label of vv₁ is q − 1 and vv_j is q + 2 j − 3 for 2 ≤ j ≤ n. Also, the wedge uv₁ is 1. Therefore, the induced edge labels of G = {1,3,5,...,2m − 1,2m + 3,...,4m + 7} and has 2m + 4 distinct edges.

Hence the vertex labels and the induced edge labels of G are distinct.

Thus G = K_1,m ∧ K_1,n is an odd mean graph when n = m + 3.

Therefore, G = K_1,m ∧ K_1,n is an odd mean graph when |m − n| ≤ 3.

Part B

Now we shall assume that G = K_1,m ∧ K_1,n is an odd mean graph and prove that |m − n| ≤ 3.

That is to prove the graph G = K_1,m ∧ K_1,n is not an odd mean graph when |m − n| > 3.

Let us prove this by the method of induction. Consider the graph when m = 1 and |m − n| = 4 that is n = 5.

G = K_1,1 ∧ K_1,5 then the vertex and edge set of G is given by,

V (G) = {u,v} ∪ {u₁} ∪ {v_j : 1 ≤ j ≤ 5} ⇒ p = 8

E (G) = {uu₁} ∪ {vv_j : 1 ≤ j ≤ 5} ∪ {w} ⇒ q = 7.

Now we shall prove that distinct vertex labels cannot be allotted to the vertices, on considering all the possible value for the vertex v (without loss of generality). The vertex labeling, f : V (G) → {0,1,2,...,2q − 1 = 13}.

Case:a

Let us first consider f (v) = 13.

The vertices should be labeled as such all the edges receives distinct odd label.

We should get 5 distinct odd labels for the edges of K_1,5.

The possibilities of the vertices are 0 or 1, 4 or 5, 8 or 9 and 12.

There are only four possibilities to label five vertices, which is not sufficient.

Therefore, G is not an odd mean graph when f (v) = 13.

Case:b

Let us first consider f (v) = 12.

The vertices should be labeled as such all the edges receives distinct odd label.

We should get 5 distinct odd labels for the edges of K_1,5.

The possibilities of the vertices are 1 or 2, 5 or 6, 9 or 10 and 13.

There are only four possibilities to label five vertices, which is not sufficient.

Therefore, G is not an odd mean graph when f (v) = 12.

Case:c

Let us first consider f (v) = 11.

The vertices should be labeled as such all the edges receives distinct odd label.

We should get 5 distinct odd labels for the edges of K_1,5.

The possibilities of the vertices are 2 or 3, 6 or 7 and 10.

There are only three possibilities to label five vertices, which is not sufficient.

Therefore, G is not an odd mean graph when f (v) = 11.

Case:d

Let us first consider f (v) = 10.

The vertices should be labeled as such all the edges receives distinct odd label.

We should get 5 distinct odd labels for the edges of K_1,5.

The possibilities of the vertices are 0, 3 or 4, 7 or 8 and 11 or 12.

There are only four possibilities to label five vertices, which is not sufficient.

Therefore, G is not an odd mean graph when f (v) = 12.

Case:e

Let us first consider f (v) = 9.

The vertices should be labeled as such all the edges receives distinct odd label.

We should get 5 distinct odd labels for the edges of K_1,5.

The possibilities of the vertices are 0 or 1, 4 or 5, 8 and 12 or 13.

There are only four possibilities to label five vertices, which is not sufficient.

Therefore, G is not an odd mean graph when f (v) = 9.

Case:f

Let us first consider f (v) = 8.

The vertices should be labeled as such all the edges receives distinct odd label.

We should get 5 distinct odd labels for the edges of K_1,5.

The possibilities of the vertices are 1 or 2, 5 or 6, 9 or 10 and 13.

There are only four possibilities to label five vertices, which is not sufficient.

Therefore, G is not an odd mean graph when f (v) = 8.

Case:g

Let us first consider f (v) = 7.

The vertices should be labeled as such all the edges receives distinct odd label.

We should get 5 distinct odd labels for the edges of K_1,5.

The possibilities of the vertices are 2 or 3, 6 or 7 and 10 or 11.

There are only three possibilities to label five vertices, which is not sufficient.

Therefore, G is not an odd mean graph when f (v) = 7.

Case:h

Let us first consider f (v) = 6.

The vertices should be labeled as such all the edges receives distinct odd label.

We should get 5 distinct odd labels for the edges of K_1,5.

The possibilities of the vertices are 0, 3 or 4, 7 or 8 and 11 or 12.

There are only four possibilities to label five vertices, which is not sufficient.

Therefore, G is not an odd mean graph when f (v) = 6.

Case:i

Let us first consider f (v) = 5.

The vertices should be labeled as such all the edges receives distinct odd label.

We should get 5 distinct odd labels for the edges of K_1,5.

The possibilities of the vertices are 0 or 1, 4 or 5, 8 or 9 and 12 or 13.

There are only four possibilities to label five vertices, which is not sufficient.

Therefore, G is not an odd mean graph when f (v) = 5.

Case:j

Let us first consider f (v) = 4.

The vertices should be labeled as such all the edges receives distinct odd label.

We should get 5 distinct odd labels for the edges of K_1,5.

The possibilities of the vertices are 1 or 2, 5 or 6, 9 or 10 and 13.

There are only four possibilities to label five vertices, which is not sufficient.

Therefore, G is not an odd mean graph when f (v) = 4.

Case:k

Let us first consider f (v) = 3.

The vertices should be labeled as such all the edges receives distinct odd label.

We should get 5 distinct odd labels for the edges of K_1,5.

The possibilities of the vertices are 2, 6 or 7 and 10 or 11.

There are only three possibilities to label five vertices, which is not sufficient.

Therefore, G is not an odd mean graph when f (v) = 3.

Case:l

Let us first consider f (v) = 2.

The vertices should be labeled as such all the edges receives distinct odd label.

We should get 5 distinct odd labels for the edges of K_1,5.

The possibilities of the vertices are 0, 3 or 4, 7 or 8 and 11 or 12.

There are only four possibilities to label five vertices, which is not sufficient.

Therefore, G is not an odd mean graph when f (v) = 2.

Case:m

Let us first consider f (v) = 1.

The vertices should be labeled as such all the edges receives distinct odd label.

We should get 5 distinct odd labels for the edges of K_1,5.

The possibilities of the vertices are 0, 4 or 5, 8 or 9 and 12 or 13.

There are only four possibilities to label five vertices, which is not sufficient.

Therefore, G is not an odd mean graph when f (v) = 1.

Case:n

Let us first consider f (v) = 0.

The vertices should be labeled as such all the edges receives distinct odd label.

We should get 5 distinct odd labels for the edges of K_1,5.

The possibilities of the vertices are 1 or 2, 5 or 6, 9 or 10 and 13.

There are only four possibilities to label five vertices, which is not sufficient.

Therefore, G is not an odd mean graph when f (v) = 0.

Therefore, G = K_1,1 ∧ K_1,5 is not an odd mean graph.

By the method of induction assume that the result is true for all m ≥ k − 1. Now consider the graph when m = k.

G = K_1,k ∧ K_1,k+4, then the vertex and edge set of G is given by,

V (G) = {u,v} ∪ {u_i : 1 ≤ i ≤ k} ∪ {v_j : 1 ≤ j ≤ k + 4} ⇒ p = 2k + 6

E (G) = {uu_i : 1 ≤ i ≤ k} ∪ {vv_j : 1 ≤ j ≤ k + 4} ∪ {w} ⇒ q = 2k + 5.

The vertex labeling, f : V (G) → {0,1,2,...,2q − 1 = 4k + 9}.

By the induction method we know that when m = k − 1 the result is true, that is the graph G = K_1,k−1 ∧ K_1,k+3 with 2k + 4 vertices and 2k + 3 edges and vertex label f : V (G) → {0,1,2,...,2q − 1 = 4k + 5} has only 2k + 3 choices of labels to label 2k + 4 vertices. Then the graph G = K_1,k ∧ K_1,k+4 with 2k + 6 vertices and 2k + 5 edges and vertex label f : V (G) → {0,1,2,...,2q − 1 = 4k + 9} will have 2k + 3 + 2 = 2k + 5 choices of label to label 2k + 6 vertices. Hence G = K_1,m ∧ K_1,n is not an odd mean graph when |m − n| = 4.

We have proved that G = K_1,m ∧ K_1,n is not an odd mean graph when |m − n| = 4, it may also be noted that when the difference between m and n increases the choices will be still less and G will not be an odd mean graph for greater differences.

Therefore G = K_1,m ∧ K_1,n is not an odd mean graph when |m − n| ≥ 3.

Hence the theorem.

The odd mean labeling is applied on a graph (network) in order to enhance fastness, efficient communication and various issues,

Researchers may get the use of odd mean labeling in their research concerned with the above discussed issues.