Product Cordial Graph in the Context of Some Graph Operations on Gear Graph

Show more

1. Introduction

We begin a simple, finite, undirected graph, where and are vertex set and edge set respectively. For all other terminology, we follow Gross [1] . Now, we provide a brief summary of definitions and other information which are necessary for the present investigations.

Definition 1. If the vertices or edges or both of the graph are assigned values subject to certain conditions then it is known as vertex, edge, total labeling respectively.

For latest survey on graph labeling, we refer to Gallian [2] . Vast amount of literature is available on different types of graph labeling and more than 1000 papers have been published.

Definition 2. A mapping is called binary vertex labeling of G and is called the label of the vertex v of G under f.

Definition 3. Given for each edge uv assign the label . Then, f is said to be a cordial labeling of G if the number of vertices with label 0 and the number of vertices with label 1 differ atmost by 1, and the number of edges with label 0 and the number of edges with label 1 differ by atmost 1.

Definition 4. A product cordial labeling of graph G with vertex set V is a function such that each edge uv is assigned the label, the number of vertices with label 0 and the number of vertices with label 1 differ by atmost 1 and the number of edge with label 0 and the number of edge with label 1 differ by atmost 1. A graph which admits a product cordial labeling is called a product cordial graph.

The notion product cordial labeling was introduced by Sundaram, Ponraj and Soma- sundaram [3] . They proved that following graphs are product cordial graph: tree, unicyclic graph of odd order, triangular snakes, dragons and helms. Vaidya and Barasara [4] also proved few results on product cordial graph. They showed that following graphs are product cordial: gear graph obtained from wheel graph if and only if n is odd, web graph, flower graph and closed helm.

Definition 5. The neighborhood of a vertex v of a graph is the set of all vertices adjacent to v. It is denoted by.

Definition 6. Duplication of a vertex of the graph G is the graph obtained from G by adding a new vertex to G such that.

Definition 7. Duplication of a vertex by a new edge in a graph G produces a new graph such that and.

Definition 8. Duplication of an edge by a new vertex w in a graph G produces a new graph such that.

The notions of duplication of a vertex by a new edge and duplication of an edge by a new vertex were introduced by Vaidya and Barasara [5] .

Definition 9. For a graph G and a vertex v of G, define a vertex switching as the graph obtained from G by removing all edges incident to v and adding edges joining v to every vertex not adjacent to v in G.

The notion vertex switching was introduced by Vaidya, Srivastav, Kaneria, and Kanani [6] .

Definition 10. The graph is called wheel graph and the vertex corre- sponding to is called an apex vertex and vertices corresponding to are called rim vertices.

Definition 11. A gear graph is obtained from the wheel graph by adding a vertex between every pair of adjacent vertices of the n-cycle.

2. Main Results

Theorem 1. The graph obtained by duplication of each vertex of degree two in the gear graph is not a product cordial graph.

Proof. Let be the wheel graph with the apex vertex and consecutive rim vertices. To obtain the gear graph subdivide each of the rim edges of the wheel graph by the vertices respectively. Obviously and. Let G be the graph obtained from by duplicating each vertex of degree two by a vertex respectively for. Thus and.

Case 1: n is odd. Label the first vertices of the sequence

each with label 0 and the re- maining vertices with label 1.

Hence, we get and. Thus.

Thus, it does not admit product cordial labeling.

Case 2: n is even. Label the first vertices of the sequence

each with label 0 and remain- ing vertices with label 1.

Hence, we get and. Thus.

Select two vertices a and b from the sequence having label 0 and 1 respectively. If we interchange the label of a and b than increases and consequently decreases. Thus

Let A and B be the set of all vertices with label 0 and 1 respectively. If we interchange the labels of k many vertices from set A to k many vertices of set B then increases and consecently decreases.

So the graph G does not admit product cordial labeling. Hence, G is not a product cordial graph.

Theorem 2. The graph obtained by duplication of each vertex of degree two by an edge in the gear graph is a product cordial graph.

Proof. Let be the wheel graph with the apex vertex and consecutive rim vertices. To obtain the gear graph subdivide each of the rim edges of the wheel graph by the vertices respectively. Obviously and. Let G be the graph obtained from by duplicating each vertex of degree two by an edge respectively for all. Thus and.

Define a function as follows:

Thus, , and. Clearly and. Thus, G admits product cordial labeling. Hence G is a product cordial graph.

Illustration 1. The product cordial labeling of the graph obtained by duplication of each vertex of degree two by an edge in gear graph for and are shown in Figure 1.

Figure 1. For and.

Theorem 3. The graph obtained by duplication of each vertex of degree three by an edge in the gear graph is a product cordial graph.

Proof. Let be the wheel graph with the apex vertex and consecutive rim vertices. To obtain the gear graph subdivide each of the rim edges of the wheel graph by the vertices respectively. Obviously and. Let G be the graph obtained from by duplicating each vertex of degree three by an edge respectively for all. Thus and.

Define a function as follows,

Thus, , , and.Clearly and. So G admits product cordial labeling. Hence, G is a product cordial graph.

Illustration 2. The product cordial labeling of the graph obtained by duplication of each vertex of degree three by an edge in gear graph for and is shown in Figure 2.

Theorem 4. The graph obtained by duplication of the apex vertex in the gear graph by an edge admits product cordial labeling if n is even.

Figure 2. For and.

Proof. Let be the wheel graph with the apex vertex and consecutive rim vertices. To obtain the gear graph subdivide each of the rim edges of the wheel graph by the vertices respectively. Obviously and. Let G be the graph obtained from by duplicating the apex vertex by an edge, clearly and.

Label the first vertices of the sequence each with label 0 and the remaining vertices with label 1. Thus,

, and. Therfore and

. So it admits product cordial labeling for all even n. Hence G is a product cordial graph.

Illustration 3. The product cordial labeling of the graph obtained by duplication of the apex vertex by an edge in gear graph for is shown in Figure 3.

Theorem 5. The graph obtained by switching of a vertex of degree two in gear graph is a product cordial graph.

Proof. Let be the wheel graph with the apex vertex and consecutive rim vertices. To obtain the gear graph subdivide each of the rim edges of by the vertices respectively. Obviously and. Let G be the graph obtain by switching the vertex in. Clearly, and.

Case 1: n is odd. Label the first n vertices of the sequence

each with label 0 and the remaining vertices each with label 1. Thus, , and.

Figure 3. For.

Case 2: n is even.

Subcase I:

Label first vertices from the sequence with label 0. Also label first vertices from the sequence with

label 0 and the remaining vertices each with label 1.

Subcase II:

Label first vertices from the sequence with label 0. Also label first vertices from the sequence

with label 0 and the remaining vertices each with label 1.

From both the subcases we get, , and.

Clearly from both the cases and. Thus G admits product cordial labeling. Hence G is a product cordial graph.

Illustration 4. The graph obtained by switching of a vertex of degree two in gear graph for is shown in Figure 4.

Figure 4. For.

Theorem 6. The graph obtained by applying vertex switching on a single vertex of degree three in gear graph is a product cordial graph.

Proof. Let be the wheel graph with the apex vertex and consecutive rim vertices. To obtain the gear graph subdivide each of the rim edges of the wheel graph by the vertices respectively. Obviously and. Let be the graph obtain by ap- plying vertex switching operation on the vertex. Clearly, and.

Case 1: n is odd. Label the first n vertices of the sequence

each with label 0 and the remaining vertices with

label 1. Thus, , and.

Case 2: n is even. Label the first n vertices of the sequence

each with label 0 and the remaining vertices with

label 1. By this labeling we get, , and

.

Clearly from both the cases and. Thus from both the cases G admits product cordial labeling. Hence G is a product cordial graph.

Illustration 5. The graph obtained by switching of a vertex of degree three in gear graph for is shown in Figure 5 as follows:

Figure 5. For.

Observation 1. The graph obtained by applying vertex switching on the apex vertex in gear graph is a product cordial graph if n is odd and it is not product cordial graph if n is even.

The graph obtained by vertex switching of the apex vertex in the gear graph again yields us a gear graph. Vaidya and Barasara [4] have already proved it in their paper that gear graph is a product cordial graph if n is odd and it is not a product cordial graph if n is even.

Conjecture 1. The graph obtained by duplication of each vertex of degree three in the gear graph is not a product cordial graph.

Conjecture 2. The graph obtained by duplication of the apex vertex in the gear graph is not a product cordial graph.

Conjecture 3. The graph obtained by switching of a vertex of degree two in gear graph is a product cordial graph.

3. Conclusion

We have derived seven results on product cordial labeling of some graphs obtained by duplication of some graph elements in gear graph. Also, we have derived two results on product cordial labeling of some graphs obtained by switching of a vertex of different degrees in the gear graph. Similar problems can be discussed for the graph obtained by duplication of an edge in gear graph. Also, the product cordial labeling can be discussed in the context of these graph operations of wheel graph, helm graph and crown graph.

Acknowledgements

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. and Yellen, J. (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.

[3] Sundaram, M., Ponraj, R. and Somasundaram, S. (2004) Product Cordial Labeling of Graphs. Bulletin of Pure & Applied Sciences—Mathematics & Statistics, 23E, 155-163.

[4] Vaidya, S.K. and Barasara, C.M. (2012) Further Results on Product Cordial Labeling. International Journal of Mathematical Combinatorics, No. 3, 64-71.

[5] Vaidya, S.K. and Barasara, C.M. (2011) Product Cordial Graphs in the Context of Some Graph Operations. International Journal of Computing Science and Mathematics, 1, 1-6.

[6] Vaidya, S.K., Srivastav, S., Kaneria, V.J. and Kanani, K.K. (2010) Some Cycle Related Cordial Graphs in the Context of Vertex Switching. Proceedings of International Conference on Discrete Mathematics, 2008 RMS Lecturer Note Series, No. 13, 243-252.