Edge Product Cordial Labeling of Some Cycle Related Graphs

Udayan M. Prajapati¹, Nittal B. Patel²

¹St. Xavier’s College, Ahmedabad, India.
²Shankersinh Vaghela Bapu Institute of Technology, Gandhinagar, India.

DOI: 10.4236/ojdm.2016.64023                

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.

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. SF₆ 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,

andSo and

Case 2: If n is odd, define the mapping as follows:

In view of the above defined labeling pattern we have,

andSo 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.

Conflicts of Interest

The authors declare no conflicts of interest.

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.