## One Modulo Three Mean Labeling of Graphs

**P. Jeyanthi**^{1,}, **A. Maheswari**^{2}

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

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

1. Introduction and Definitions

2. One Modulo Three Mean Labeling

3. One Modulo Three Mean Labeling of Some Trees

### 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

**Keywords:** one modulo three mean labeling, one modulo three mean graph

*American Journal of Applied Mathematics and Statistics*, 2014 2 (5),
pp 302-306.

DOI: 10.12691/ajams-2-5-2

Received July 31, 2014; Revised August 25, 2014; Accepted August 28, 2014

**Copyright**© 2013 Science and Education Publishing. All Rights Reserved.

### 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 *B*_{m,n}_{ }is a graph obtained from *K*_{2} by joining m pendant edges to one end of *K*_{2}_{ }and *n* pendant edges to the other end of *K*_{2}. The edge of *K*_{2 }is called the central edge of *B*_{m,n}_{ }and the vertices of* K*_{2}* *are called the central vertices of *B*_{m}_{,n}.

**Definition ****1.4****:** Let T be a tree with at least four vertices. Let *u*_{0} and *v*_{0} 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 u_{0}-u path is equal to the length of *v*_{0}-*v* path. If the edge *u*_{0}*v*_{0} 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 u_{0}v_{0} is called transformable edge. If by applying a sequence of ept’s, T can be reduced to a path, then T is called a T_{p}-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 3*q*-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*(3*q*-1)-*t**.*

Hence, .

As an illustration, we consider the cycle graph *C*_{5}=

Define : V (*C*_{5})→ 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 *C*_{3}=*uvwu*. If * *is an one modulo three mean labeling of G then and for any *x,y*.

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

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

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

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

(ii) Suppose that *uv* is an edge of G with =3*x**+1 *and =3*x*+3 then the induced edge label of *uv** *is 3*x*+2. This is a contradiction to the fact that the edge labels are congruent to one modulo three. Therefore, 3*x*+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 *P*_{n}* *is a one modulo three mean graph if *n* is even.

**Proof:** Let V (P_{n}) = and E(P_{n})= . Define the vertex labeling : V (P_{n})→ 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 *P*_{n}. Therefore, *P*_{n}(*n* is even) is a one modulo three mean graph.

An example for one modulo three mean labeling of the graph *P*_{8}_{ }is given in Figure1.

**Figure 1**.

**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_{2}. 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*_{1}, *V*_{2}) be the bipartition of *K*_{1, n}^{ }with *V*_{1}= and *V*_{2}=. 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 3*n*-2. This contradiction proves that *K*_{1,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 *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*_{m}_{ }*nK*_{1}_{ }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*_{4}_{ }is given in Figure 2.

**Figure 2**.

**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 3*q*-2 and 3q-3. Suppose that* *either 3*q*-2 or 3*q*-3. 3*q*-2 = 3*m*+3*n*+1 > 6n+1. Therefore, > 3n+1 and > 3*n*. Hence, the labels of the edges and *uv* are greater than 3*n**+1*. But the set contains only m elements, whereas the edges and* uv* are m+1 in number. Hence, 3*q*-2 and 3*q*-3.

Next, we prove that 3*q*-2 and 3*q*-3. Suppose* *that either 3*q*-2 or 3*q*-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, 3*q*-2 and 3*q*-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, 3*q*- 2 and 3*q*-3.

Also 3*q*-2 or 3*q*-3 cannot be the label for any of the vertices since otherwise 3*q*-2 or 3*q*-3 will be the label for *u*. Similarly 3*q*-2 or 3*q*-3 cannot be the label for any of the vertices *.* Therefore, 3*q*-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*_{1}*, P*_{2}*,..., 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*_{1}*,v*_{2}*,…,v*_{n}_{ }starting 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*_{i}*v*_{j} be an edge of *T* for some indices* i *and *j*, 1 ≤ *i* ≤ *n* and let *P*_{1} be the ept that deletes this edge and adds the edge *v*_{i+t}*v*_{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*_{1} as one of the constituent epts. Since v_{i+t}v_{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*_{i}*v*_{j} is given by,

Hence, we have^{*}(*v*_{i}*v*_{j})= *(*v*_{i+t}*v*_{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**.

### 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*_{n}_{ }is a one modulo three mean graph if *n*≡1(mod4).

**Proof:** Let *n** *= 4*k*+1. Let *v*_{1}_{,}_{ }*v*_{2 }_{,}*…, 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*_{n}_{ }is a one modulo three mean graph if *n*≡1(mod4).

An example for one modulo three mean labeling of the graph C_{13 }is given in Figure4.

**Figure 4**.

**Theorem**** 4.2****:** The ladder graph *L*_{n}_{ }*=P*_{n}*×P*_{2}* *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*_{1})=0, * *(*u*_{n})=9(*n*-1), (*u*_{2i})=18*i*-11

if 1 ≤ *i* ≤, (*u*_{2i+1})=18*i*+6 if 1 ≤ *i* ≤-1 and (*v*_{1})=1, (*v*_{n})=9*n* - 8, (*v*_{2i})=6(3*i*-1)

if 1 ≤* i* ≤ ,(*v*_{2i+1})=18*i*-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_{7}_{ }is given in Figure 5.

**Figure 5**.

If *G*_{1} and *G*_{2} are two graphs then *G*_{1} *G*_{2} is the Cartesian product of ^{[1]} *G*_{1} and *G*_{2}*.*

**Theorem**** 4.3****:**** **The graph** **K_{1,n} K_{2} is a one modulo three mean graph if n is even

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

An example for one modulo three mean labeling of the graph K_{1,}_{4} K_{2}_{ }is given in Figure 6.

**Figure 6**.

**Theorem**** 4.4****:** The complete graph *K*_{n} is a one modulo three mean graph if and only if n ≤ 2.

**Proof:** Suppose *K*_{n}* *is a one modulo three mean graph. To get the edge label 3*q*-2, we must have 3*q*-2 and 3*q*-3 as the vertex labels. Let *u* and *v* be the vertices whose labels are 3*q*-2 and 3*q*-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 *K*_{n} is not a one modulo three mean graph for n >3. If n = 2, the complete graph *K*_{2} is a path P_{2}, 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 | |||