One Modulo Three Mean Labeling of Graphs

Veiw figure View Figure

Theorem 3.2: The star graph K_{1, n}is a one modulo three mean graph if and only if n = 1.

Proof: If n = 1, the star graph K_1,1 is a path P₂. Hence K_1,1 is a one modulo three mean graph.

Conversely assume that n ≥ 2. Suppose K_{1, n}is a one modulo three mean graph with one modulo three mean labeling . Let (V₁, V₂) be the bipartition of K_{1, n}with V₁= and V₂=. To get the edge label 1, we must have 0 and 1 as the labels of the adjacent vertices. Therefore, either (u)=0 or (u)=1. In both the cases there is no edge with the label 3n-2. This contradiction proves that K_1,nis not a one modulo three mean graph for n ≥ 2.

Theorem 3.3: The caterpillar G obtained by attaching n pendant edges to each vertex of the path P_m is a one modulo three mean graph if m≡0(mod2).

Proof: Let G be a caterpillar obtained from the path P_m = by attaching n pendant edges to each of its vertices. Let u_ij, 1≤ j ≤ n be the vertices attached to the vertex u_i, 1≤ i ≤ m of P_m then G is isomorphic to P_mnK₁and it has m(n+1) vertices and m(n+1)-1 edges.

Define : V (G)→ as follows: For 1≤ i ≤ m, 1≤ j ≤ n

then the induced edge labels are . Hence, is one modulo three mean labeling. Therefore, the caterpillar G obtained by attaching n pendant edges to each vertex of the path P_m is a one modulo three mean graph.

An example for one modulo three mean labeling of the graph P₄is given in Figure 2.

Figure 2.

Download as

Veiw figure View Figure

Corollary 3.4: The comb graph and the Bistar B_n,n are one modulo three mean graphs.

Theorem 3.5: The bistar B_m_,n, is a one modulo three mean graph if and only if m = n.

Proof: If m = n, by Corollary 3.4 B_m_,n is a one modulo three mean graph. Conversely assume that B_m_,n is a one modulo three mean graph with m ≠ n. Without loss of generality, assume that m > n. Let the vertex set V(B_m_,n) =and the edge set E(B_m_,n) =. Clearly B_m_,n has m+n+2 vertices and q = m+n+1 edges. Let be the one modulo three mean labeling of B_m_,n.

First, we prove that 3q-2 and 3q-3. Suppose that either 3q-2 or 3q-3. 3q-2 = 3m+3n+1 > 6n+1. Therefore, > 3n+1 and > 3n. Hence, the labels of the edges and uv are greater than 3n+1. But the set contains only m elements, whereas the edges and uv are m+1 in number. Hence, 3q-2 and 3q-3.

Next, we prove that 3q-2 and 3q-3. Suppose that either 3q-2 or 3q-3. Since q > 2 there is an edge with label 1. Hence, either = 0 or = 0 for some i.

If = 0 then the labels of the edges , uv are less than or equal to . Since m > n, m+1 > . Therefore, the number of elements in the set is less than m+1whereas the edges and uv are m+1 in number. Hence, 3q-2 and 3q-3.

If =0 for some i then must be 1. Hence, the labels of the edges and uv are less than or equal to . But the number of elements in the set is less than m+1 whereas the edges and uv are m+1 in number. Hence, 3q- 2 and 3q-3.

Also 3q-2 or 3q-3 cannot be the label for any of the vertices since otherwise 3q-2 or 3q-3 will be the label for u. Similarly 3q-2 or 3q-3 cannot be the label for any of the vertices . Therefore, 3q-2 is not a label for any vertex. Hence, B_m_,n, m > n is not a one modulo three mean graph.

Theorem 3.6: A T_p-tree with even number of vertices is a one modulo three mean graph.

Proof: Let T be a T_p-tree with |V(T)| = n where n is even. By the definition of a transformed tree there exists parallel transformation P of T such that P(T) is a path. For the path P(T) we have (i)V(P(T)) = V(T) (ii)E(P(T)) = (E(T) \ E_d) ∪ E_p where E_d is the set of edges deleted from T and E_p is the set of edges newly added through the sequence P = (P₁, P₂,..., P_k) of the epts P used to arrive the path P(T). Clearly E_d and E_p have the same number of edges. Denote the vertices of P(T) successively as v₁,v₂,…,v_nstarting from one pendant vertex of P(T) right up to the other.

Define : V(P(T)) → by

for 1 ≤ i ≤ n. Clearly is one modulo three mean labeling of the path P(T).

Let v_iv_j be an edge of T for some indices i and j, 1 ≤ i ≤ n and let P₁ be the ept that deletes this edge and adds the edge v_i+tv_j-t where t is the distance from v_i to v_i+t and also the distance from v_j to v_j-t. Let P be a parallel transformation of T that contains P₁ as one of the constituent epts. Since v_i+tv_j-t is an edge of the path P(T), it follows that i + t + 1 = j - t which implies j = i + 2t +1. The induced label of the edge v_iv_j is given by,

Hence, we have^*(v_iv_j)= *(v_i+tv_j-t) and therefore is one modulo three mean labeling of the T_p -tree T.

An example for one modulo three mean labeling of a T_p-tree with 18 vertices is given in Figure 3.

Figure 3.

Download as

Veiw figure View Figure

4. One Modulo Three Mean Labeling of Cycle Related Graphs

In this section, we prove that some cycle related graphs are one modulo three mean graphs.

Theorem 4.1: Cycle C_nis a one modulo three mean graph if n≡1(mod4).

Proof: Let n = 4k+1. Let v₁_,v₂_,…, v_n be the vertices of C_n.

Define : V(C_n)→ by

The induced edge labels of the cycle C_n are . Hence, C_nis a one modulo three mean graph if n≡1(mod4).

An example for one modulo three mean labeling of the graph C₁₃is given in Figure4.

Figure 4.

Download as

Veiw figure View Figure

Theorem 4.2: The ladder graph L_n=P_n×P₂ is a one modulo three mean graph if n is odd.

Proof: Let the vertex set of L_n be and the edge set of L_n be . Clearly L_n has 2n vertices and 3n-2 edges.

Define : V( C_n)→ by (u₁)=0, (u_n)=9(n-1), (u_2i)=18i-11

if 1 ≤ i ≤, (u_2i+1)=18i+6 if 1 ≤ i ≤-1 and (v₁)=1, (v_n)=9n - 8, (v_2i)=6(3i-1)

if 1 ≤ i ≤ ,(v_2i+1)=18i-5 if 1 ≤ i ≤-1. Hence, the induced edge labels of L_n are then is one modulo three mean labeling. Hence, L_n is a one modulo three mean graph.

An example for one modulo three mean labeling of the graph L₇is given in Figure 5.

Figure 5.

Download as

Veiw figure View Figure

If G₁ and G₂ are two graphs then G₁ G₂ is the Cartesian product of ^[1] G₁ and G₂.

Theorem 4.3: The graph K_1,n K₂ is a one modulo three mean graph if n is even

Proof: Let the vertices of K_1,n K₂ be and edges are .Clearly K_1,n K₂ has 2n+2 vertices and 3n+1 edges. Define : V(K_1,n K₂)→ by (u)=0, (v)=9n+1, (u_n+1-i)=12i - 5 if 1 ≤ i ≤ , (u_i)=12i - 11 if 1 ≤ i ≤ and (v_n+1-i)=9n - 6(i-1) if 1 ≤ i ≤ , (v_i)=6n - 6(i-1) if 1 ≤ i ≤ . The induced edge labels of K_1,n K₂ are then is one modulo three mean labeling. Hence, K_1,n K₂ is a one modulo three mean graph.

An example for one modulo three mean labeling of the graph K_1,₄ K₂is given in Figure 6.

Figure 6.

Download as

Veiw figure View Figure