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 Hn-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 kn,n is H-Cordial if and only if n > 2 and “n” is even; and km,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 kn is H-Cordial if and only if n ≡ 0 or 3 (mod4) and n ≠ 3. Wn is H-Cordial if and only if n is odd. kn is not H2-Cordial if n ≡ 1 (mod4). Also [2] prove that every wheel has an H2-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 = G1 + G2 of graph G1 and G2 with disjoint point sets V1 and V2 and edge sets E1 and E2 denoted by G = G1 + G2 is the graph union together with all the edges joining v1, v2. If G1 is (p1,q1) graph and G2 is (p2,q2) graph then is a.
1.2. Definition: Let G1 = (V1, E1) and G2 = (V2, E2) be two graphs. The Cartesian product of G1 and G2 which is denoted by G1G2 is the graph with vertex set v = v1 × v2 consisting of vertices u and v are adjacent in whenever u1 = v1 and u2 adjacent to v2 or u1 adjacent to v1 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 Cn of even order admits a Zero-M-Cordial labeling Proof: Let be the vertices of cycle Cn
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 C6. 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 C8. 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 km,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 km,n. The number of vertices and the edges of km,n is m + n and mn respectively.
Define f:
Table 1. The vertex and the edge conditions of cycle graph Cn.
Figure 1. Zero-M-Cordial labeling on C6.
Figure 2. Zero-M-Cordial labeling on C8.
The edge matrix of km,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 k4,4.
Using Table 2 the edge label matrix of k4,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 bipartite graph K4,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 K4,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 K2,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 k2,4 admits a zero-M-cordial labeling.
Figure 4 illustrates the Zero-M-Cordial labeling on k2,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 k2,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 Km,n.
Figure 3. Zero-M-Cordial labeling on k4,4.
Figure 4. Zero-M-Cordial labeling on k2,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 k2,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 k2,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 Cn and Cm
Figure 5. Zero-M-Cordial labeling on k2,6.
admits a Zero-M-Cordial labeling if n + m 0 (mod 4).
Proof: Let and are the vertex set of the cycles Cn and Cm. The edge set E1 and E2 is the graph union of Cn and Cm together with all the edges joining the vertex set and.
We note that and.
Define f:
The edge matrix of cn + cm 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 C4 + C4. Using Table 4 the edge label matrix of C4 & C4 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 C4 and C4 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 c4 + c4. 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 Cn, for even n, admits
Table 5. The vertex and the edge conditions of two cycle graphs Cn and Cm.
Figure 6. Zero-M-Cordial Labeling on C4 + C4.
a zero-M-cordial labeling.
Proof:
Let be the vertices of cycle Cn and be the newly added vertices when n is even.
Let G be the split graph of cycle Cn 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 Cn 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 Cn.
Table 7. Vertex and the edge condition of.
Figure 7. Zero-M-Cordial labeling on split C8.
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.
.
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.