Open Journal of Discrete Mathematics
Vol.06 No.04(2016), Article ID:70490,11 pages
10.4236/ojdm.2016.64021
Some Edge Product Cordial Graphs in the Context of Duplication of Some Graph Elements
Udayan M. Prajapati1, Prakruti D. Shah2
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, a function
is called an edge product cordial labeling of G, if the induced vertex labeling function is defined by the product of the labels of the incident edges as such that the number of edges with label 1 and the number of edges with label 0 differ by at most 1 and the number of vertices with label 1 and the number of vertices with label 0 differ by at most 1. In this paper, we show that the graphs obtained by duplication of a vertex, duplication of a vertex by an edge or duplication of an edge by a vertex in a crown graph are edge product cordial. Moreover, we show that the graph obtained by duplication of each of the vertices of degree three by an edge in a gear graph is edge product cordial. We also show that the graph obtained by duplication of each of the pendent vertices by a new vertex in a helm graph is edge product cordial.
Keywords:
Graph Labeling, Edge Product Cordial Labeling, Duplication of a Vertex
1. Introduction
We begin with a simple, finite, undirected graph where
and
denote the vertex set and the edge set respectively. For all other ter- minology, we follow Gross [1] . We will provide a brief summary of definitions and other information which are necessary for the present investigations.
Definition 1. A graph labeling is an assignment of integers to the vertices or edges or both subject to certain condition. If the domain of the mapping is the set of vertices, edges or both then the labeling is called a vertex labeling, an edge labeling or a total labeling.
Definition 2. For a graph G, an edge labeling function is defined as and the induced vertex labeling function
is given by
if
are the edges incident with the vertex v.
We denote the number of vertices of G having label i under by
and the number of edges of G having label i under f by
for
.
The function f is called an edge product cordial labeling of G if and
. A graph G is called edge product cordial if it admits edge product cordial labeling.
The concept of edge product cordial labeling was introduce by Vaidya and Barasara [2] in which they proved that for n odd, trees of order greater than 2, unicyclic graphs of odd order, crowns, armed crowns, helms, closed helms, webs, flowers graph are edge product cordial. They also proved that wheel and gear for even are not edge product cordial. They also [3] proved that
,
for odd,
for odd,
for odd are edge product cordial labeling. They also proved that
for even,
for even,
for even,
are not edge product cordial labeling.
Definition 3. The graph is called wheel graph, the vertex corre- sponding to
is called apex vertex and vertices corresponding to
are called rim vertices.
Definition 4. The helm is the graph obtained from a wheel
by attaching a pendent edge at each vertex of the n-cycle.
Definition 5. A gear graph is obtained from the wheel graph by adding a vertex between every pair of adjacent vertices of the n-cycle.
Definition 6. The crown is obtained by joining a single pendent edge to each vertex of
.
Definition 7. The neighborhood of a vertex v of a graph is the set of all vertices adjacent to v. It is denoted by.
Definition 8. Duplication of a vertex of the graph G is the graph obtained from G by adding a new vertex
to G such that
.
Definition 9. Duplication of a vertex by a new edge
in a graph G
produces a new graph such that
and
.
The concept of duplication of vertex by edge was introduce by Vaidya and Barasara [4] .
Definition 10. Duplication of an edge by a new vertex w in a graph G produces a new graph
such that
.
The concept of duplication of edge by vertex was introduce by Vaidya and Dani [5] .
2. Main Results
Theorem 1. The graph obtained by duplication of an arbitrary vertex of the cycle in a crown graph is an edge product cordial graph.
Proof. Let be a cycle with consecutive vertices
and edges
for each
. Let
be a new vertex adjacent to
with
for each
. Resulting graph is a crown graph
.
Let G be the graph obtained by duplication of the vertex by a new vertex
of
such that
,
and
.
Thus and
.
Now for and
Figure 1 shows that the graphs are edge product cordial as follows:
Figure 1. and
.
Case 1: When n is odd. For, define
as follows:
In the view of above labeling pattern we have,
and
.
Case 2: When n is even. For, define
as follows:
In the view of the above labeling pattern we have,
and
.
Thus, from both the cases we have and
.
Hence, graph G admits edge product cordial labeling. Thus, G is an edge product cordial graph.
□Illustration 1. The graph obtained by duplication of an arbitrary vertex of the cycle in a crown graph is an edge product cordial graph as shown in Figure 2 as follows:
Figure 2. and
.
Theorem 2. The graph obtained by duplication of an arbitrary vertex of the cycle by a new edge in a crown graph is edge product cordial graph.
Proof. Let be a cycle with consecutive vertices
and edges
for each
. Let
be a new vertex adjacent to
with
for each
. Resulting graph is a crown graph
.
Let G be the graph obtained by duplication of the vertex by an edge
of
such that
and
. Thus
and
. Define
as follows:
In the view of the above labeling pattern we have, and
. Thus, we have
and
.
Hence, graph G admits edge product cordial labeling. Thus, G is an edge product cordial graph.
□Illustration 2. The graph obtained by duplication of an arbitrary vertex of the cycle by a new edge in a crown graph is edge product cordial graph as shown in Figure 3.
Figure 3..
Theorem 3. The graph obtained by duplication of an arbitrary edge of the cycle by a new vertex in a crown graph is edge product cordial.
Proof. Let be a cycle with the consecutive vertices
and edges
for each
. Let
be a new vertex adjacent to
with
for each
. Resulting graph is a crown graph
.
Let G be the graph obtained by duplication of an edge by a vertex
in
such that
and
. Thus
and
. Define
as follows:
In the view of above labeling pattern we have,and
. Thus, we have
and
.
Hence, graph G admits edge product cordial labeling. Thus, G is an edge product cordial graph.
□Illustration 3. The graph obtained by duplication of an arbitrary edge of the cycle by a new vertex in a crown graph is edge product cordial graph as shown in Figure 4.
Figure 4..
Theorem 4. The graph obtained by duplication of each pendent vertex by a new vertex in a crown graph is edge product cordial graph.
Proof. Let be a cycle with consecutive vertices
and edges
for each
. Let
be a new vertex adjacent to
with
for each
. Resulting graph is a crown graph
.
Let G be the graph obtained by duplication of each pendent vertex by a new vertex
of
such that
for
. Thus
and
.
Case 1: When n is odd, define as follows:
In the view of above labeling pattern we have,and
.
Case 2: When n is even, define as follows:
In the view of above labeling pattern we have, and
.
Thus, from both the cases we have and
. Hence, graph G admits edge product cordial labeling. Thus, G is an edge product cordial graph.
□Illustration 4. The graph obtained by duplication of each pendent vertex by a new vertex in a crown graph is edge product cordial graph as shown in Figure 5 as follows:
Figure 5. and
.
Theorem 5. The graph obtained by duplication of each of the vertices of degree three by an edge in a gear graph is an edge product cordial graph.
Proof. Let be the wheel graph with apex vertex v and consecutive rim vertices
. To obtained the gear graph
subdivide each of the rim edges
of the wheel graph by the vertices
respectively such that
,
and
for
.
Let G be the graph obtained from by duplication of each vertex
by an edge
such that
and
for
. Thus
and
.
Define as follows:
In the view of the above labeling pattern we have, and
. Thus, we have
and
. Hence, graph G admits edge product cordial labeling. Thus, G is edge product cordial graph.
□Illustration 5. The graph obtained by duplication of each vertex of degree three by an edge in a gear graph is an edge product cordial graph as shown in Figure 6.
Figure 6..
Theorem 6. The graph obtained by duplication of each of the pendent vertices by a new vertex in a helm graph is edge product cordial graph.
Proof. Let v be the apex vertex and be the consecutive rim vertices of the wheel
with edges
and
for
. Let
be a new vertex adjacent to
with edges
for
. Resulting graph is helm graph
.
Let G be the graph obtained from by duplication of each pendent vertex
by a new vertex
such that
for
. Thus
and
.
Case 1: When n is odd, define as follows:
In the view of above labeling pattern we have, and
.
Case 2: When n is even, define as follows:
In the view of above labeling pattern we have, and
.
Thus, from both the cases we have and
. Hence, graph G admits edge product cordial labeling. Thus, G is an edge product cordial graph.
□Illustration 6. The graph obtained by duplication of each pendent vertex by a new vertex in a helm graph is edge product cordial graph as shown in Figure 7.
Figure 7. and
.
3. Conclusion
We have derived six results for edge product cordial related to crown graph, gear graph and helm graph in the context of duplication of various graph elements. Similar pro- blem can be discussed for other graph family for edge product cordial labeling.
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 Shah, P.D. (2016) Some Edge Product Cordial Graphs in the Context of Duplication of Some Graph Elements. Open Journal of Discrete Mathematics, 6, 248-258. http://dx.doi.org/10.4236/ojdm.2016.64021
References
- 1. Gross, J.L. and Yellen, J. (Eds.) (2004) Handbook of Graph Theory. CRC Press, Boca Raton.
- 2. Vaidya, S.K. and Barasara, C.M. (2012) Edge Product Cordial Labeling of Graphs. Journal of Mathematics and Computer Science, 2, 1436-1450.
http://scik.org/index.php/jmcs/article/view/420/189 - 3. Vaidya, S.K. and Barasara, C.M. (2013) Some New Families of Edge Product Cordial Graphs. Advanced Modeling Optimization, 15, 103-111.
http://camo.ici.ro/journal/vol15/v15a9.pdf - 4. Vaidya, S.K. and Barasara, C.M. (2011) Product Cordial Graphs in the Context of Some Graph Operations. International Journal of Mathematics and Computer Science, 1, 1-6.
- 5. Vaidya, S.K. and Dani, N.A. (2011) Cordial and 3-Equitable Graphs Induced by Duplication of Edge. Mathematics Today, 27, 71-82.