** Applied Mathematics ** Vol. 3 No. 11 (2012) , Article ID: 24510 , 8 pages DOI:10.4236/am.2012.311228

Zero-M-Cordial Labeling of Some Graphs

Department of Mathematics, Scott Christian College, Nagercoil, India

Email: freedasam1969@gmail.com, robinchel@rediffmail.com

Received August 14, 2012; revised September 28, 2012; accepted October 5, 2012

**Keywords:** Zero-M-Cordial Labeling; Split Graphs; Cartesian Product; H-Cordial

ABSTRACT

In this paper we prove that the complete bipartite graph k_{m}_{,n} where m and n are even, join of two cycle graphs c_{n} and c_{m} where (mod 4), split graph of c_{n} for even “n”, where n is even are admits a Zero-M-Cordial labeling. Further we prove that of odd n admits a Zero-M-Cordial labeling.

1. Introduction

We begin with finite, connected and undirected graph G = (V(G), E(G). If the vertices of the graph are assigned values subject to certain conditions then it is known as graph labeling. Any graph labeling will have the following three common characteristics. A set of numbers from which Vertex labels are chosen; = number of vertices of G having label i under f

= number of edges of G having label i under f*.

The concept of cordial labeling was introduced by I. Cahit, who called a graph G is Cordial if there is a vertex labeling such that the induced labeling

, defined by

, for all edges and with the following inequalities holding and

and.

In [1] introduced the concept of H-Cordial labeling. Cahit calls a graph H-Cordial if it is possible to label the edges with the numbers from the set in such a way that, for some k, at each vertex v the sum of the labels on the edges incident with v is either k or –k and the inequalities and

are also satisfied where v(i)and e(j) are respectively, the number of vertices labeled with i and the number of edges labeled with j. He calls a graph H_{n}-Cordial if it is possible to label the edges with the numbers from the set in such a way that, at each vertex v the sum of the labels on the edges incident with v is in the set and the inequalities and are also satisfied for each i with. The concept of Zero-M-Cordial labeling is defined in [2]. A labeling f of a graph G is called Zero-M-Cordial, if for each vertex v, f(v) = 0. A graph G is called to be Zero-M-Cordial, if it admits a Zero-M-Cordial labeling. The usefulness of the above definition appears when one tries to find an HCordial labeling for a given graph G. If H is a ZeroM-Cordial subgraph of G then H-Cordiality of G\E(H) simply implies H-Cordiality G.

In [1] proved that k_{n}_{,n} is H-Cordial if and only if n > 2 and “n” is even; and k_{m}_{,n}, m ≠ n is H-Cordial if and only if n ≡ 0 (mod4), m is even and m > 2, n > 2.

In [2] proved that k_{n} is H-Cordial if and only if n ≡ 0 or 3 (mod4) and n ≠ 3. W_{n} is H-Cordial if and only if n is odd. k_{n} is not H2-Cordial if n ≡ 1 (mod4). Also [2] prove that every wheel has an H_{2}-Cordial labeling.

In [3] several variations of graph labeling such as graceful, bigraceful, harmonious, cordial, equitable, humming etc. have been introduced by several authors. For definitions and terminologies in graph theory we refer to [4].

In this paper we investigate Zero-M-Cordial labeling on some Cartesian product of graphs, join of two graphs, and bipartite graph.

1.1. Definition: The join G = G_{1} + G_{2} of graph G_{1} and G_{2} with disjoint point sets V_{1} and V_{2} and edge sets E_{1} and E_{2} denoted by G = G_{1} + G_{2} is the graph union together with all the edges joining v_{1}, v_{2}. If G_{1} is (p_{1},q_{1}) graph and G_{2} is (p_{2},q_{2}) graph then is a.

1.2. Definition: Let G_{1} = (V_{1}, E_{1}) and G_{2} = (V_{2}, E_{2}) be two graphs. The Cartesian product of G_{1} and G_{2} which is denoted by G_{1}G_{2} is the graph with vertex set v = v_{1} × v_{2} consisting of vertices u and v are adjacent in whenever u_{1} = v_{1} and u_{2} adjacent to v_{2} or u_{1} adjacent to v_{1} and.

1.3. Definition: For a graph G the split graph is obtained by adding to each vertex, a new vertex such that is adjacent to every vertex that is adjacent to in G. The resultant graph is denoted by spl (G).

2. Main Results

Theorem 2.1: Every cycle C_{n} of even order admits a Zero-M-Cordial labeling Proof: Let be the vertices of cycle C_{n}

Define f: two cases are to be considered.

Case (i) n 2 (mod 4)

For

In view of the above labeling pattern we give the proof as follows:

When n 2 (mod 4)

The total number of edges labeled with are given by and the total number of edges labeled with are given by. Therefore the total difference between the edges labeled with and are given by. The induced vertex labels are equal to zero. Thus for each vertex v, and.

Case (ii) n 0 (mod 4)

The total number of edges labeled with are given by and the total number of edges labeled with are given by. Therefore the total difference between the edges labeled with and are given by. The induced vertex labels are equal to zero. Thus for each vertex v, and.

Hence the cycle graph cn, even n admits a zero-Mcordial labeling.

The vertex and the edge conditions are given in Table 1. The illustration is given in Figures 1 and 2.

In Figure 1 illustrates the Zero-M-Cordial labeling for the cycle graph C_{6}. Among the six edges three edges receive the label +1 and the other three edges receive the label –1. In Figure 2 illustrates the Zero-M-Cordial labeling for the cycle graph C_{8}. Among the eight edges four edges receive the label +1 and the other four edges receive the label –1.

Theorem 2.2: The complete bipartite graph k_{m}_{,n} admits a Zero-M-Cordial labeling for all m, n such that m + n 0, 2 (mod 4).

Proof: Let and are the vertex set of the bipartite graph k_{m}_{,n}. The number of vertices and the edges of k_{m}_{,n} is m + n and mn respectively.

Define f:

Table 1. The vertex and the edge conditions of cycle graph C_{n}.

Figure 1. Zero-M-Cordial labeling on C_{6}.

Figure 2. Zero-M-Cordial labeling on C_{8}.

The edge matrix of k_{m}_{,n} is given in Table 2.

In view of the above edge matrix we give the proof as follows.

Case (i) when m + n 0 (mod 4), m = n.

Consider the bipartite graph k_{4,4}.

Using Table 2 the edge label matrix of k_{4,4} is given by

Table 2. Edge matrix of k_{m}_{,n}.

With respect to the above labeling the total number of edges labeled with and are given by and. Therefore the total difference between the edges labeled with and are given by. The induced vertex labels are equal to zero. Thus for each vertex v, and._{}

Hence the bipartite graph K_{4,4} admits a Zero-M-Cordial labeling. The vertex and the edge conditions are given in Table 3. The illustration is given in Figure 3.

Figure 3 illustrates the Zero-M-Cordial labeling on K_{4,4}. Among the Sixteen edges eight edges receive the label +1 and the other eight edges receive the label –1.

Case (ii) When m + n 2 (mod 4),.

Consider the bipartite graph K_{2}_{,4}.

Using Table 2 the edge label matrix is given by

With respect to the above labeling the total number of edges labeled with and are given by . Therefore the total difference between the edges labeled with and are given by. The induced vertex labels are equal to zero. Thus for each vertex v, and.

Hence the bipartite graph k_{2,4} admits a zero-M-cordial labeling.

Figure 4 illustrates the Zero-M-Cordial labeling on k_{2,4}. Among eight edges four edges receive the label +1 and other four edges receive the label –1.

Case (iii) When m + n 0 (mod 4) and.

Consider the bipartite graph k_{2,6}.

Using Table 2 the edge label matrix is given by

With respect to the above labeling the total number of edges labeled with and are given by

Table 3. The vertex and the edge conditions of the bipartite graph K_{m}_{,n}.

Figure 3. Zero-M-Cordial labeling on k_{4,4}.

Figure 4. Zero-M-Cordial labeling on k_{2,4}.

and. Therefore the total difference between the edges labeled with and are given by. The induced vertex labels are equal to zero. Thus for each vertex v, and.

Hence the bipartite graph k_{2,6} admits a Zero-M-Cordial labeling. The vertex and the edge conditions are given in Table 3.

Figure 5 illustrates the Zero-M-Cordial labeling on k_{2,6}. Among the Twelve edges six edges receive the label +1 and the other six edges receive the label –1.

Theorem 2.3: The join of two cycle graphs C_{n} and C_{m}

Figure 5. Zero-M-Cordial labeling on k_{2,6}._{}

admits a Zero-M-Cordial labeling if n + m 0 (mod 4).

Proof: Let and are the vertex set of the cycles C_{n} and C_{m}. The edge set E1 and E2 is the graph union of C_{n} and C_{m} together with all the edges joining the vertex set and.

We note that and.

Define f:

The edge matrix of c_{n} + c_{m} is given in Table 4.

In view of the above labeling pattern we give the proof as follows:

When n + m 0 (mod 4)

Consider the join of two cycle graphs C_{4} + C_{4}. Using Table 4 the edge label matrix of C_{4} & C_{4} is given by

With respect to the above labeling the total number of edges labeled with and are given by and. Therefore the total difference between the edges labeled with and are given by. The induced vertex labels are equal to zero. Thus for each vertex v, and.

Hence the join of two cycle graphs C_{4} and C_{4} admits a Zero-M-Cordial labeling. The vertex and the edge conditions are given in Table 5.

In Figure 6 illustrates the zero-M-Cordial labeling on c_{4} + c_{4}. Among the twenty four edges twelve edges receive the label +1 and the other twelve edges label –1.

Theorem 2.4: The split graph of C_{n}, for even n, admits

Table 4. Edge matrix of C_{n} + C_{m}.

Table 5. The vertex and the edge conditions of two cycle graphs C_{n} and C_{m}.

Figure 6. Zero-M-Cordial Labeling on C_{4} + C_{4}.

a zero-M-cordial labeling.

Proof:

Let be the vertices of cycle C_{n} and be the newly added vertices when n is even.

Let G be the split graph of cycle C_{n} with

,

we note that and.

Define two cases are to be considered.

Case (i) when n 0 (mod 4)

For

For

For

Case (ii) when n 2 (mod 4)

For

For

For

With respect to the above labeling pattern we give the proof as follows.

The total number of edges labeled with and are given by and. Therefore the total difference between the edges labeled with and are given by differ by zero. The induced vertex labels are equal to zero. Thus for each vertex v, and.

Hence the split graph of C_{n} for even n admits a ZeroM-Cordial labeling. The vertex and the edge conditions are given in Table 6.

In Figure 7 illustrates the Zero-M-Cordial labeling on split c8. Among the twenty four edges twelve edges receive the label +1 and the other twelve edges receive the label –1.

Theorem 2.5: admits a Zero-M-Cordial labeling for even n.

Proof: Let G be the graph where n is even and be the vertices of the graph G.

We note that and as

and

Define as follows For

For

For

For

For

With respect to the above labeling pattern we give the proof as follows.

The total number of edges labeled with and are given by and. Therefore the total difference between the edges labeled with and are given by differ by 0. The induced vertex labels are equal to zero. Thus for each vertex v, and.

Hence admits a Zero-M-Cordial labeling for even n. The vertex and the edge conditions are given in Table 7.

Figure 8 illustrates the Zero-M-Cordial labeling on. Among the sixteen edges eight edges label +1 and the other eight edges label –1.

Theorem 2.6: admits a Zero-M-Cordial labeling for odd n.

Proof: Let G be the graph where n is odd and be the vertices of graph G.

We note that and

as and

Table 6. The vertex and the edge conditions of split of C_{n}.

Table 7. Vertex and the edge condition of.

Figure 7. Zero-M-Cordial labeling on split C_{8}.

Figure 8. Zero-M-Cordial labeling on.

Define as follows For

For

For

For

For

The total number of edges labeled with and are given by and. Therefore the total difference between the edges labeled with and are given by differ by 0. The induced vertex labels are equal to zero. Thus for each vertex v, and.

Hence admits a Zero-M-Cordial labeling for odd n. The vertex and the edge conditions are given in Table 8.

Figure 9 illustrates the Zero-M-Cordial labeling on. Among the sixteen edges eight edges receive the label +1 and the other eight edges label –1.

Theorem 2.7: (also known as book graph) admits a Zero-M-Cordial labeling for odd n.

Proof: Let G be the graph where n is odd and be the vertices of G.

We note that and.

Define as follows For

For

For

For

For

For

The total number of edges labeled with and are given by and. Therefore the total difference between the edges labeled with

and are given by

differ by 0. The induced vertex labels are equal to zero. Thus for each vertex v, and

Table 8. Vertex and the edge condition of.

Table 9. Vertex and the edge condition of.

Figure 9. Zero-M-Cordial labeling on.

Figure 10. Zero-M-Cordial labeling on.

.

Hence (also known as book graph) admits a Zero-M-Cordial labeling for odd n. The vertex and the edge conditions are given in Table 9.

Figure 10 illustrates Zero-M-Cordial labeling on. Among the ten edges five edges receive the label +1 and the other five edges receive the label –1.

3. Concluding Remark

Here we investigate Zero-M-Cordial labeling for Cartesian product of some graphs, join of two cycle graphs, split graphs and bipartite graphs. Similar results can be derived for other graph families and in the context of different graph labeling problem is an open area of research.

REFERENCES

- I. Cahit, “H-Cordial Graphs,” Bulletin of the Institute of Combinatorics and Its Applications, Vol. 18, 1996, pp. 87-101.
- M. Ghebleh and R. Khoeilar, “A Note on ‘H-Cordial graphs’,” Bulletin of the Institute of Combinatorics and Its Applications, Vol. 31, 2001, pp. 60-68.
- J. A. Gallian, “A Dynamic Survey of Graph Labeling,” The Electronics Journal of Combinatories, Vol. 18, 2011.
- F. Harary, “Graph Theory,” Addison Wesley, Reading, 1972.