Product Cordial Graph in the Context of Some Graph Operations on Gear Graph ()
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.
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.
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
.
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.
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:
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.