One Modulo Three Mean Labeling of Graphs

P. Jeyanthi, A. Maheswari

  Open Access OPEN ACCESS  Peer Reviewed PEER-REVIEWED

One Modulo Three Mean Labeling of Graphs

P. Jeyanthi1,, A. Maheswari2

1Department of Mathematics, Govindammal Aditanar College for Women, Tiruchendur, Tamilnadu, India

2Department of Mathematics, Kamaraj College of Engineering and Technology, Virudhunagar, Tamilnadu, India

Abstract

In this paper, we introduce a new labeling called one modulo three mean labeling. A graph G is said to be one modulo three mean graph if there is an injective function from the vertex set of G to the set {a | 0 ≤ a ≤ 3q-2 and either a≡0(mod 3) or a≡1(mod 3) } where q is the number of edges of G and induces a bijection from the edge set of G to given by and the function is called one modulo three mean labeling of G. Furthermore, we prove that some standard graphs are one modulo three mean graphs.

At a glance: Figures

Cite this article:

  • Jeyanthi, P., and A. Maheswari. "One Modulo Three Mean Labeling of Graphs." American Journal of Applied Mathematics and Statistics 2.5 (2014): 302-306.
  • Jeyanthi, P. , & Maheswari, A. (2014). One Modulo Three Mean Labeling of Graphs. American Journal of Applied Mathematics and Statistics, 2(5), 302-306.
  • Jeyanthi, P., and A. Maheswari. "One Modulo Three Mean Labeling of Graphs." American Journal of Applied Mathematics and Statistics 2, no. 5 (2014): 302-306.

Import into BibTeX Import into EndNote Import into RefMan Import into RefWorks

1. Introduction and Definitions

All graphs considered here are simple, finite, connected and undirected. We follow the basic notations and terminologies of graph theory as in [1].Given a graph G, the symbols V (G) and E (G) denote the vertex set and the edge set of the graph G, respectively. Let G= G(p, q) be a graph with p = |V(G)| vertices and q = |E(G)| edges. A graph labeling is an assignment of integers to the vertices or edges or both, subject to certain conditions. There are several types of graph labeling and a detailed survey is available in [2].

V. Swaminathan and C.Sekar introduced the concept of one modulo three graceful labeling in [5]. S.Somasundram and R.Ponraj introduced mean labeling of graphs in [3] and further studied in [4]. Motivated by the work of these authors we introduce a new type of labeling known as one modulo three mean labeling and prove that some standard graphs are one modulo three mean graphs. We use the following definitions in the subsequent sections.

Definition 1.1: A comb graph is a graph obtained by joining a single pendant edge (vertex with degree one) to each vertex of a path.

Definition 1.2: A caterpillar is a tree with the property that the removal of its end vertices (vertices with degree one) leaves a path.

Definition 1.3: Bistar Bm,n is a graph obtained from K2 by joining m pendant edges to one end of K2 and n pendant edges to the other end of K2. The edge of K2 is called the central edge of Bm,n and the vertices of K2 are called the central vertices of Bm,n.

Definition 1.4: Let T be a tree with at least four vertices. Let u0 and v0 be the two adjacent vertices of T and let u and v be the leaves of T with the property that the length of the u0-u path is equal to the length of v0-v path. If the edge u0v0 is deleted from T and u and v are joined by an edge uv, then such a transformation of T is called an elementary parallel transformation (or an ept) and the edge u0v0 is called transformable edge. If by applying a sequence of ept’s, T can be reduced to a path, then T is called a Tp-tree (transformed tree) and such a sequence regarded as a composition of mappings (ept’s) denoted by P, is called a parallel transformation of T. The path, the image of T under P is denoted as P(T).

For any integer n, denotes the smallest integer not less than n.

2. One Modulo Three Mean Labeling

Definition 2.1: A graph G is said to be one modulo three mean graph if there is an injective function from the vertex set of G to the set {a | 0 ≤ a ≤ 3q-2 and either a 0(mod 3) or a 1(mod 3) } where q is the number of edges of G and induces a bijection from the edge set of G to {a | 1 ≤ a ≤ 3q-2 and a 1(mod 3) }given by *(uv) = and the function is called one modulo three mean labeling of G.

Remark: If G is a one modulo three mean graph with more than two edges then 0, 1, 3(q-1) and 3q-2 must be the vertex labels.

Theorem 2.2: Let G be a one modulo three mean graph with one modulo three mean labeling . Let t be the number of edges whose one vertex label is even and the other label is odd then where d (v) denotes the degree of a vertex v.

Proof: Since is one modulo three mean labeling of G, we have *(xy) = .

Now = = q(3q-1)-t.

Hence, .

As an illustration, we consider the cycle graph C5=

Define : V (C5)→ by () = 0, () = 1, () = 7, ()=12, () = 13. Clearly is one modulo three mean labeling. Here t=4.

Now

Theorem 2.3: Let G be a one modulo three mean graph containing a cycle C3=uvwu. If is an one modulo three mean labeling of G then and for any x,y.

Proof: Suppose . Assume = 3x+1, =3x+6y+1, =3x+6y then the edges u v and u w get the same label 3x+3y+1 which is not possible.

Suppose. Assume =3x, =3x+1, =3x+6y+1 then the edges u w and v w get the same label 3x+3y+1 which is not possible.

Theorem 2.4: Let G be a one modulo three mean graph then (i) 3x and 3x+4 cannot be the labels of the adjacent vertices and (ii) 3x+1 and 3(x+1) cannot be the labels of the adjacent vertices (iii) 3x and 3y cannot be the labels of the adjacent vertices and (iv) 3x+1 and 3x+4 cannot be the labels of adjacent vertices.

Proof: (i) Suppose that uv is an edge of G with =3x and =3x+4 then the induced edge label of uv is 3x+2. This is a contradiction to the fact that the edge labels are congruent to one modulo three. Therefore, 3x and 3x+4 cannot be the labels of the adjacent vertices.

(ii) Suppose that uv is an edge of G with =3x+1 and =3x+3 then the induced edge label of uv is 3x+2. This is a contradiction to the fact that the edge labels are congruent to one modulo three. Therefore, 3x+1 and 3(x+1) cannot be the labels of the adjacent vertices.

On the same line, we can prove (iii) and (iv).

3. One Modulo Three Mean Labeling of Some Trees

Theorem 3.1: The path Pn is a one modulo three mean graph if n is even.

Proof: Let V (Pn) = and E(Pn)= . Define the vertex labeling : V (Pn)→ by () = 6(i-1), 1≤ i ≤ and () = 6(i-1)+1, 1≤ i ≤ , then the induced edge labels are . Hence is a one modulo three mean labeling of Pn. Therefore, Pn(n is even) is a one modulo three mean graph.

An example for one modulo three mean labeling of the graph P8 is given in Figure1.

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

Proof: If n = 1, the star graph K1,1 is a path P2. Hence K1,1 is a one modulo three mean graph.

Conversely assume that n ≥ 2. Suppose K1, n is a one modulo three mean graph with one modulo three mean labeling . Let (V1, V2) be the bipartition of K1, n with V1= and V2=. 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 K1,n is 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 Pm is a one modulo three mean graph if m≡0(mod2).

Proof: Let G be a caterpillar obtained from the path Pm = by attaching n pendant edges to each of its vertices. Let uij, 1≤ j ≤ n be the vertices attached to the vertex ui, 1≤ i ≤ m of Pm then G is isomorphic to Pm nK1 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 Pm is a one modulo three mean graph.

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

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

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

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

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

Proof: Let T be a Tp-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) \ Ed) Ep where Ed is the set of edges deleted from T and Ep is the set of edges newly added through the sequence P = (P1, P2,..., Pk) of the epts P used to arrive the path P(T). Clearly Ed and Ep have the same number of edges. Denote the vertices of P(T) successively as v1,v2,…,vn starting from one pendant vertex of P(T) right up to the other.

Define : V(P(T))by

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

Let vivj be an edge of T for some indices i and j, 1 ≤ in and let P1 be the ept that deletes this edge and adds the edge vi+tvj-t where t is the distance from vi to vi+t and also the distance from vj to vj-t. Let P be a parallel transformation of T that contains P1 as one of the constituent epts. Since vi+tvj-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 vivj is given by,

Hence, we have*(vivj)= *(vi+tvj-t) and therefore is one modulo three mean labeling of the Tp -tree T.

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

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 Cn is a one modulo three mean graph if n≡1(mod4).

Proof: Let n = 4k+1. Let v1, v2 ,…, vn be the vertices of Cn.

Define : V(Cn)→ by

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

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

Theorem 4.2: The ladder graph Ln =Pn×P2 is a one modulo three mean graph if n is odd.

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

Define : V( Cn )→ by (u1)=0, (un)=9(n-1), (u2i)=18i-11

if 1 ≤ i, (u2i+1)=18i+6 if 1 ≤ i-1 and (v1)=1, (vn)=9n - 8, (v2i)=6(3i-1)

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

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

If G1 and G2 are two graphs then G1 G2 is the Cartesian product of [1] G1 and G2.

Theorem 4.3: The graph K1,n K2 is a one modulo three mean graph if n is even

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

An example for one modulo three mean labeling of the graph K1,4 K2 is given in Figure 6.

Theorem 4.4: The complete graph Kn is a one modulo three mean graph if and only if n ≤ 2.

Proof: Suppose Kn is a one modulo three mean graph. To get the edge label 3q-2, we must have 3q-2 and 3q-3 as the vertex labels. Let u and v be the vertices whose labels are 3q-2 and 3q-3 respectively. Again, to get the edge label 1, we must have 0 and 1 as the vertex labels. Let w and z be the vertices whose labels are 0 and 1 respectively then the edges uw, vz receive the same induced label which should not happen. Hence Kn is not a one modulo three mean graph for n >3. If n = 2, the complete graph K2 is a path P2, which is a one modulo three mean graph.

References

[1]  F.Harary, Graph theory, Addison Wesley, Massachusetts, (1972).
In article      
 
[2]  J. A. Gallian, A dynamic survey of graph labeling, The Electronic Journal of Combinatorics, DS6, 2013.
In article      
 
[3]  S. Somasundaram and R. Ponraj, Mean Labeling of graphs, National Academy Science Letters Vol: 26,(2003), 210-213.
In article      
 
[4]  S. Somasundaram and R. Ponraj, Some results on Mean graphs, Pure and Applied Mathematika Sciences, Vol: 58 (2003), 29-35.
In article      
 
[5]  V. Swaminathan and C. Sekar, Modulo three graceful graphs, Proceed. National Conference on Mathematical and Computational Models, PSG College of Technology, Coimbatore, 2001, 281-286.
In article      
 
  • CiteULikeCiteULike
  • MendeleyMendeley
  • StumbleUponStumbleUpon
  • Add to DeliciousDelicious
  • FacebookFacebook
  • TwitterTwitter
  • LinkedInLinkedIn