Open Journal of Discrete Mathematics
Vol.06 No.04(2016), Article ID:70492,11 pages
10.4236/ojdm.2016.64023
Edge Product Cordial Labeling of Some Cycle Related Graphs
Udayan M. Prajapati1, Nittal B. Patel2
1St. Xavier’s College, Ahmedabad, India
2Shankersinh Vaghela Bapu Institute of Technology, Gandhinagar, India
Copyright © 2016 by authors and Scientific Research Publishing Inc.
This work is licensed under the Creative Commons Attribution International License (CC BY 4.0).
http://creativecommons.org/licenses/by/4.0/
Received: June 8, 2016; Accepted: September 6, 2016; Published: September 9, 2016
ABSTRACT
For a graph 
having no isolated vertex, a function 
is called an edge product cordial labeling of graph G, if the induced vertex labeling function defined by the product of labels of incident edges to each vertex is such that the number of edges with label 0 and the number of edges with label 1 differ by at most 1 and the number of vertices with label 0 and the number of vertices with label 1 also differ by at most 1. In this paper, we discuss edge product cordial labeling for some cycle related graphs.
Keywords:
Graph Labeling, Edge Product Cordial Labeling
1. Introduction
We begin with simple, finite, undirected graph 
having no isolated vertex where 
and 
denote the vertex set and the edge set respectively, 
and 
denote the number of vertices and edges respectively. For all other terminology, we follow Gross [1] . In the present investigations, 
denotes cycle graph with n vertices. We will give brief summary of definitions which are useful for the present work.
Definition 1. A graph labeling is an assignment of integers to the vertices or edges or both subject to the certain conditions. If the domain of the mapping is the set of vertices (or edges) then the labeling is called a vertex (or an edge) labeling.
For an extensive survey on graph labeling and bibliography references, we refer to Gallian [2] .
Definition 2. For a graph G, the edge labeling function is defined as 
and induced vertex labeling function 
is given as if 
are all the edges incident to the vertex v then
.
Let 
be the number of vertices of G having label i under 
and 
be the number of edges of G having label i under f for
.
f is called an edge product cordial labeling of graph G if 
and
. A graph G is called edge product cordial if it admits an edge product cordial labeling.
Vaidya and Barasara [3] introduced the concept of the edge product cordial labeling as an edge analogue of the product cordial labeling.
Definition 3. The wheel 
is the graph obtained by adding a new vertex joining to each of the vertices of
. The new vertex is called the apex vertex and the vertices corresponding to 
are called rim vertices of
. The edges joining rim vertices are called rim edges.
Definition 4. The helm 
is the graph obtained from a wheel 
by attaching a pendant edge to each of the rim vertices.
Definition 5. The closed helm 
is the graph obtained from a helm 
by joining each pendant vertex to form a cycle. The cycle obtained in this manner is called an outer cycle.
Definition 6. The web 
is the graph obtained by joining the pendant vertices of a helm 
to form a cycle and then adding a pendant edge to each of the vertices of the outer cycle.
Definition 7. The Closed Web graph 
is the graph obtained from a web graph 
by joining each of the outer pendent vertices consecutively to form a cycle.
Definition 8. [4] The Sunflower graph 
is the graph obtained by taking a wheel with the apex vertex 
and the consecutive rim vertices 
and additional vertices 
where 
is joined by edges to 
and
.
Definition 9. [4] The Lotus inside a circle 
is a graph obtained from a cycle 
and a star graph 
with center vertex 
and end vertices 
by joining each 
to 
and
.
Definition 10. [5] Duplication of a vertex v of a graph G produces a new graph 
by adding a new vertex 
such that
. In other words, 
is said to be a duplication of v if all the vertices which are adjacent to v in G are also adjacent to 
in
.
Definition 11. [5] Duplication of a vertex 
by a new edge 
in a graph G produces a new graph 
such that 
and
.
Definition 12. The Flower graph 
is the graph obtained from a helm 
by joining each pendant vertex to the apex of the helm
.
2. Main Result
Theorem 1. Closed web graph 
is not an edge product cordial graph.
Proof. Let 
be the apex vertex and 
be the consecutive rim vertices of
. Let
, for each 
(here subscripts are modulo n). Let
. Let 
be the new vertices corresponding to 
respectively. Form the edge 
by joining 
and
. Form the cycle by creating edges
. The resulting graph is called a helm graph. Let 
be the new vertices corresponding to 
respec- tively. Form the edge 
by joining 
and
. Form the cycle by creating the edges
. The resulting graph is a closed web graph
. Thus 
and
. We are trying to define the mapping 
we consider following two cases:
Case 1: If n is odd then in order to satisfy the edge condition for edge product cordial graph it is essential to assign label 0 to 3n edges out of 6n edges. So in this context, the
edges with label 0 will give rise at least 
vertices with label 0 and at most 
vertices with label 1 out of 
vertices. Therefore
. So
is not an edge product cordial graph for odd n.
Case 2: If n is even then in order to satisfy the edge condition for edge product cordial graph it is essential to assign label 0 to 3n edges out of 6n edges. So in this
context, the edges with label 0 will give rise at least 
vertices with label 0 and at most 
vertices with label 1 out of 
vertices.
From both the cases
, so 
is not an edge product cordial graph.
Theorem 2. Lotus inside circle 
is not an edge product cordial graph.
Proof. Let 
be the apex vertex and 
be the consecutive vertices of star graph
. Let 
for each
. Let 
be the new vertices corresponding to 
respectively. Form the cycle by creating the edges
. Let 
and
. The re- sulting graph is Lotus inside circle
. Thus 
and
. We are trying to define the mapping
. In order to satisfy an edge condition for edge product cordial graph it is essential to assign label 0 to 2n edges out of 4n edges. So in this context, the edges with label 0 will give rise to at least 
vertices with label 0 and at most 
vertices with label 1 out of 
vertices. Therefore
.
So, 
is not an edge product cordial graph.
Theorem 3. Sunflower graph 
is an edge product cordial graph for
.
Proof. Let 
be the sunflower graph, where 
is the apex vertex, 
be the consecutive rim vertices of 
and 
be the additional vertices where 
is joined to 
and
. Let 
be the consecutive rim edges of the
. 
are the corresponding edges joining apex vertex 
to the vertices 
of the cycle. Let for each
, 
be the edges joining 
to 
and 
be the edges joining 
to
. Thus 
and
. Define the mapping 
as follows:
In view of the above defined labeling pattern we have, 
and
. So, 
and
. Thus 
and
. Thus f admits an edge product cordial on
. Hence, 
is an edge product cordial graph.
Illustration 1. Graph 
and its edge product cordial labeling is shown in Figure 1.
Theorem 4. The graph obtained from duplication of each of the vertices 
for 
by a new vertex in the sunflower graph 
is an edge product cordial graph if and only if n is even.
Proof. Let 
be sunflower graph, where 
is the apex vertex, 
be the consecutive rim vertices of 
and 
be the additional vertices where 
is joined to 
and
. Let 
be the consecutive rim edges of the
. 
are the corresponding edges joining the apex vertex 
to the vertices 
of the cycle. Let for each
, 
be the edges joining 
to 
and 
be the edges joining 
to
. Let G be the graph obtained from 
by duplication of the vertices 
by the new vertices 
respectively. Let for each
, 
be the edges joining 
to 
and 
be the edges joining 
to
. Thus 
and
. We consider the following two cases:
Case 1: If n is odd, define the mapping 
in order to satisfy edge condition for edge product cordial graph it is essential to assign label 0 to 3n edges out
of 6n edges. So in this context, the edges with label 0 will give rise at least 
Figure 1. SF6 and its edge product cordial labeling
vertices with label 0 and at most 
vertices with label 1 out of 
vertices.
Therefore
. So the duplication of vertex 
by vertex 
in sunflower graph is not edge product cordial for odd n.
Case 2: If n is even, define the mapping 
as follows:
In view of the above defined labeling pattern we have,
and
.
So 
and
. Thus 
and
. Thus g admits an edge product cordial labeling on G. So, G is an edge product cordial for even n.
Illustration 2. Graph G obtained from 
by duplication of each of the vertices 
by new vertices 
and its edge product cordial labeling is shown in Figure 2.
Theorem 5. The graph obtained from duplication of each of the vertices 
for 
by a new edges 
in the sunflower graph 
is an edge product cordial graph.
Figure 2. G and its edge product cordial labeling.
Proof. Let 
be sunflower graph, where 
is the apex vertex, 
be the consecutive rim vertices of 
and 
be the additional vertices where 
is joined to 
and
. Let 
be the consecutive rim edges of
. 
are the corresponding edges joining apex vertex 
to the vertices 
of the cycle. Let for each
, 
be the edges joining 
to 
and 
be the edges joining 
to
. Let G be the graph obtained from 
by duplication of the vertices 
by corresponding new edges 
with new vertices 
and 
such that 
and 
join to the vertex
. Let for each
, 
be the edges joining the vertices 
and 
and for each
, 
be the edges joining 
to 
and 
be the edges joining 
to
. Thus 
and
. We consider the following two cases:
Case 1: If n is odd, define the mapping 
as follows:
In view of the above defined labeling pattern we have,
and 
So,
and
,
.
Case 2: If n is even, define 
as follows:
In view of the above defined labeling pattern we have,
and 
So,
and 
From both the cases 
and
. Thus, g admits an edge product cordial labeling on G. So the graph G is an edge product cordial graph.
Illustration 3. Graph G obtained from 
by duplication of each of the vertices 
by corresponding new edges 
and its edge product cordial labeling is shown in Figure 3.
Theorem 6. The graph obtained by duplication of each of the vertices in the sunflower graph 
is not an edge product cordial graph.
Proof. Let 
be the sunflower graph, where 
is the apex vertex, 
be the consecutive vertices of the cycle 
and 
be the additional vertices where 
is joined to 
and
. Let 
be the consecutive edges of the cycle
. 
are the corresponding edges joining the apex vertex 
to the vertices 
of the cycle. Let for each
, 
be the edge joining 
to 
and 
be the edge joining 
to
. Let G be the graph obtained from 
by duplication of each of the vertices
by the vertices 
respectively.
Figure 3. G and its edge product cordial labeling.
Let 
be the edges joining the vertex 
to the adjacent vertex of 
for
. 
are the edges joining the vertex 
to the adjacent vertex of 
for 
and 
are the edges joining the vertex 
to the adjacent vertex of cin the sunflower graph. Thus 
and
. We are trying to define
.
In order to satisfy the edge condition for edge product cordial graph, it is essential to assign label 0 to 6n edges out of 12n edges. So in this context, the edge with label 0 will
give rise at least 
vertices with label 0 and at most 
vertices with
label 1 out of 
vertices. Therefore,
. So the graph G is not an edge product cordial graph.
Theorem 7. The graph obtained by subdividing the edges 
and 
(subscripts are mod n) for all i = 1,2,...,n by a vertex in the sunflower graph 
is an edge product cordial.
Proof. Let 
be the sunflower graph, where 
is the apex vertex, 
be the consecutive rim vertices of 
and 
be the additional vertices where 
is joined to 
and
. Let 
be the consecutive rim edges of
. 
are the corresponding edges joining apex vertex 
to the vertices 
of the cycle. Let G be the graph obtained from 
by subdividing the edges 
and 
for all 
by a vertex 
and 
respectively. Let for each
, 
be the edges joining 
to 
and 
be the edges joining 
to
. Let for each
, 
be the edges joining 
to 
and 
be the edges joining 
to
. Thus, 
and
. We consider the following two cases:
Case 1: If n is odd, define 
as follows:
In view of the above defined labeling pattern we have,
and
. So 
and
.
Case 2: If n is even, define 
as follows:
In view of the above defined labeling pattern we have,
and
. So 
and
.
From both the cases 
and
. Thus g admits an edge product cordial labeling on G. So the graph G is an edge product cordial graph.
Illustration 4. Graph G obtained from 
by subdividing the edges 
and 
for all 
by a vertex 
and 
respectively for 
and its edge product cordial labeling is shown in Figure 4.
Theorem 8. The graph obtained by flower graph 
by adding n pendant vertices to the apex vertex 
is an edge product cordial graph.
Proof. The Flower graph 
is the graph obtained from a helm 
by joining
Figure 4. G and its edge product cordial labeling.
each pendant vertex to the apex vertex of the helm
. Let G be the graph obtained from the flower graph 
by adding n pendant vertices 
to the apex vertex
. Let 
be the rim vertices and 
be the pendant vertices to 
respectively.
Let 
be the consecutive rim edges of
. 
are the cor- responding edges joining the apex vertex 
to the vertices 
of the cycle. Let 
for each
. Let 
for each
. Let 
for each
. Thus 
and
. We consider two cases:
Case 1: If n is even, define the mapping 
as follows:
In view of the above defined labeling pattern we have,
and
So 
and
Case 2: If n is odd, define the mapping 
as follows:
In view of the above defined labeling pattern we have,
and
So 
and
,
From both the cases 
and
. Thus, f admits an edge product cordial labeling on G. So G is an edge product cordial graph.
Illustration 5. Graph G obtained from 
by adding 5 pendent vertices 
to the apex vertex 
and its edge product cordial labeling is shown in Figure 5.
Figure 5. G and its edge product cordial labeling.
3. Concluding Remarks
We investigated eight results on the edge product cordial labeling of various graph generated by a cycle. Similar problem can be discussed for other graph families.
Acknowledgements
The authors are highly thankful to the anonymous referee for valuable comments and constructive suggestions. The first author is thankful to the University Grant Commission, India for supporting him with Minor Research Project under No. F. 47-903/14 (WRO) dated 11th March, 2015.
Cite this paper
Prajapati, U.M. and Patel, N.B. (2016) Edge Product Cordial Labeling of Some Cycle Related Graphs. Open Journal of Discrete Mathematics, 6, 268-278. http://dx.doi.org/10.4236/ojdm.2016.64023
References
- 1. Gross, J.L. and Yellen, J. (Eds.) (2004) Handbook of Graph Theory. CRC Press, Boca Raton.
- 2. Gallian, J.A. (2014) A Dynamic Survey of Graph Labeling. The Electronic Journal of Combinatorics, 17, #DS6.
http://www.combinatorics.org - 3. Vaidya, S.K. and Barasara, C.M. (2012) Edge Product Cordial Labeling of Graphs. Journal of Mathematical and computational Science, 2, 1436-1450.
- 4. Ponraj, R., Sathish Narayanan, S. and Kala, R. (2015) A Note on Difference Cordial Graphs. Palestine Journal of Mathematics, 4, 189-197.
- 5. Vaidya, S.K. and Prajapati, U.M. (2013) Prime Labeling in the Context of Duplication of Graph Elements. International Journal of Mathematics and Soft Computing, 3, 13-20.