Cordial Labeling of Corona Product of Path Graph and Second Power of Fan Graph ()
1. Introduction
Labeling problem is important in graph theory. It is known that graph theory and its branches have become interesting topics for almost all fields of mathematics and also other areas of science such as chemistry, biology, physics, communication, economics, engineering, and especially computer science. A graph labeling is an assignment of integers to the vertices or edges or both. There are many contributions and different types of labeling. [1] [2] [3] [4] suppose that
is a graph, where V is the set of its vertices and E is the set of its edges. Throughout, it is assumed G is connected, finite, simple and undirected. A binary vertex labeling of G is a mapping
in which
is said to be the labeling of
. For an edge
, where
, the induced edge label
is defined by the formula
. Thus, for any edge e,
if its two vertices have the same label and
if they have different labels. Let us denote
and
be the numbers of vertices labeled by 0 and 1 in V respectively, and let
and
be the corresponding numbers of edge in E labeled by 0 and 1 respectively. A binary vertex labeling f of G is said to be cordial if
and
hold. A graph G is cordial if it has cordial labeling. Cordial graphs were introduced by Cahit [5] [6] as a weaker version of both graceful graphs and harmonious graphs [2] [3] [4]. A recommended reference on this subject is the survey by Gallian [1]. A path with n vertices and
edges is denoted by
, and second power of fan graph has
vertices and
edges is denoted by
. Let G (with
vertices and
edges) and H (with
vertices and
edges) are two graphs. The corona between G and H is the graph denoted by
and is obtained by taking one copy of G and
copies of H, and then joining the i-th vertex of G with an edge to every vertex in the i-th copy of H [9]. It follows from the definition of the corona that
has
vertices and
edges. It is easy to see that
is not in general isomorphic to
. A second power of a fan
is the graph obtained from the join of the second power of a path
and a null graph
, i.e.
. So the order of
is
and its size is
, in particular
,
and
. In this paper we study the corona
and show that is cordial for all
and
.
2. Terminology and Notation
We introduce some notation and terminology for a graph with 4r vertices [7] [8] [9]. Let
denote the labeling
, zero-one repeated r-times if r is even and
if r is odd; for example,
and
. Welet
denote the labeling
. Sometimes, we modify the labeling
or
by adding symbols at one end or the other (or both). We let
denote the labeling
(repeated r-times) where
and,
denote the labeling
(repeated r-times) where
and
denotes the labeling
(repeated r-times) and
denotes the labeling
(repeated r-times). In most cases, we then modify this by adding symbols at one end or the other (or both), thus
denotes the labeling
(repeated r-times) when
and 101 when
. Similarly,
is the labeling
(repeated r-times) when
and 1 when
. Similarly,
is the labeling
when
and 01 when
. Also, we write
for the labeling
(repeated r-times) and
for the labeling
(repeated r-times) [7] [8] [9] [10]. For specific labeling L and M of
where G is path and H is a second fans, we let
denote the corona labeling. Additional notation that we use is the following. For a given labeling of the corona
, we let
and
(for
) be the numbers of labels that are i as before, we let
and
be the corresponding quantities for G, and we let
and
be those for H, which are connected to the vertices labeled 0 of G. Likewise, let
and
be those for H, which are connected to the vertices labeled 1 of G. In case it increases by one more vertexes, so
and
will be those for H, which are connected to the vertex labeled 1 or 0 of G. It is easy to verify that,
,
and
,
.
Thus,
and
when it comes to the proof, we only need to show that, for each specified combination of labeling,
and
.
3. The Corona between Paths and Second Fans
In this section, we show that the corona between paths and second power of Fan graphs
is cordial for all
, and
. This target will be achieved after the following series of lemmas.
Lemma 3.1
is cordial for all
and
.
Proof. We need to examine the following cases:
Case (1).
.
Let
,
. Then, one can choose the labeling
for
. Therefore ,
,
,
,
,
,
,
,
,
and
. Hence, one can easily show that
and
Thus
,
is cordial.
As an example, Figure 1 illustrates
.
Figure 1. The corona between paths and second power of Fan graphs
.
Case (2).
.
Let
,
. Then, one can choose the labelling
for
. Therefore
,
,
,
,
,
,
,
,
,
,
,
,
,
and
. Hence, one can easily show that
and
. Thus
is cordial.
As an example, Figure 2 illustrates
.
Figure 2. The corona between paths and second power of Fan graphs
.
Case (3).
.
Let
,
. Then, one can choose the labelling
for
. Therefore
,
,
,
,
,
,
,
,
,
and
. Hence, one can easily show that
and
. Thus
,
is cordial.
As an example, Figure 3 illustrates
.
Figure 3. The corona between paths and second power of Fan graphs
.
Case (4).
.
Let
,
. Then, one can choose the labelling
for
. Therefore,
,
,
,
,
,
,
,
,
,
,
,
,
,
and
. Hence, one can easily show that
and
. Thus
is cordial.
As example, Figure 4 illustrates
.
Figure 4. The corona between paths and second power of Fan graphs
.
Lemma 3.2
is cordial for all
and
.
Proof. We need to examine the following cases:
Case (1).
.
Let
,
. Then, one can choose the labeling
for
. Therefore
,
,
,
,
,
,
,
and
,
. Hence, one can easily show that
and
. Thus
,
is cordial.
As an example, Figure 5 illustrates
.
Figure 5. The corona between paths and second power of Fan graphs
.
Case (2).
.
Let
,
. Then, one can choose the labeling
for
. Therefore
,
,
,
,
,
,
,
,
,
,
, and
. Hence, one can easily show that
and
. Thus
,
, is cordial.
As an example, Figure 6 illustrates
.
Figure 6. The corona between paths and second power of Fan graphs
.
Case (3).
.
Let
,
. Then, one can choose the labeling [
,
,
,
,
,
,
] for
. Therefore
,
,
,
,
,
,
,
and
,
. Hence one can easily show that
and
. Thus
,
, is cordial.
As an example, Figure 7 illustrates
.
Figure 7. The corona between paths and second power of Fan graphs
.
Case (4).
.
Let
,
. Then, one can choose the labeling [
,
,
,
,
,
,
,
] for
. Therefore
,
,
,
,
,
,
,
,
,
,
, and
. Hence, one can easily show that
and
. Thus
,
, is cordial.
As an example, Figure 8 illustrates
.
Figure 8. The corona between paths and second power of Fan graphs
.
Lemma 3.3
is cordial for all
and
.
Proof. We need to study the following cases:
Case (1).
.
Let
,
. Then, one can choose the labeling
for
. Therefore
,
,
,
,
,
,
,
,
and
. Hence, one can easily show that
and
. Thus
is cordial.
As an example, Figure 9 illustrates
.
Figure 9. The corona between paths and second power of Fan graphs
.
Case (2).
.
Let
,
. Then, one can choose the labeling
for
. Therefore
,
,
,
,
,
,
,
,
,
,
,
,
,
and
. Hence, one can easily show that
and
. Thus
,
is cordial.
As an example, Figure 10 illustrates
.
Figure 10. The corona between paths and second power of Fan graphs
.
Case (3).
.
Let
,
. Then, one can choose the labeling
for
. Therefore
,
,
,
,
,
,
,
,
and
. Hence, one can easily show that
and
. Thus
,
is cordial.
As an example, Figure 11 illustrates
.
Figure 11. The corona between paths and second power of Fan graphs
.
Case (4).
.
Let
,
. Then, one can choose the labeling
for
. Therefore
,
,
,
,
,
,
,
,
,
,
,
,
,
,
and
. Hence, one can easily show that
and
. Thus
,
is cordial.
As an example, Figure 12 illustrates
.
Figure 12. The corona between paths and second power of Fan graphs
.
Lemma 3.4
is cordial for all
and
.
Proof: Will be examined following cases:
Case (1).
.
Let
,
. Then, one can choose the labeling
for
. Therefore
,
,
,
,
,
,
,
and
,
. Hence, one can easily show that
and
. Thus
,
is cordial.
As an example, Figure 13 illustrates
.
Figure 13. The corona between paths and second power of Fan graphs
.
Case (2).
.
Let
,
. Then, one can choose the labeling
for
. Therefore
,
,
,
,
,
,
,
,
,
,
,
,
and
. Hence one can easily show that
and
. Thus
,
is cordial.
As an example, Figure 14 illustrates
.
Figure 14. The corona between paths and second power of Fan graphs
.
Case (3).
.
Let
,
. Then, one can choose the labeling
for
. Therefore
,
,
,
,
,
,
,
,
and
. Hence, one can easily show that
and
. Thus
,
is cordial.
As an example, Figure 15 illustrates
.
Figure 15. The corona between paths and second power of Fan graphs
.
Case (4).
.
Let
,
. Then, one can choose the labeling [
,
,
,
,
,
,
,
] for
. Therefore
,
,
,
,
,
,
,
,
,
,
,
,
and
. Hence one can easily show that
and
. Thus
,
is cordial.
As an example, Figure 16 illustrates
.
Figure 16. The corona between paths and second power of Fan graphs
.
As a consequence of all previous lemmas one can establish the following theorem.
Theorem. The corona between path
&
is cordial for all k and m.