Some Edge Product Cordial Graphs in the Context of Duplication of Some Graph Elements

Show more

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.

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.