Cordial Labeling of Corona Product of Path Graph and Second Power of Fan Graph
Abstract: A graph is said to be cordial if it has 0 - 1 labeling which satisfies particular conditions. In this paper, we construct the corona between paths and second power of fan graphs and explain the necessary and sufficient conditions for this construction to be cordial.

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 $G=\left(V,E\right)$ 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 $f:V\to \left\{0,1\right\}$ in which $f\left(u\right)$ is said to be the labeling of $u\in V$. For an edge $e=uv\in E$, where $u,v\in V$, the induced edge label ${f}^{*}:E\to \left\{0,1\right\}$ is defined by the formula ${f}^{*}\left(vw\right)=\left(f\left(v\right)+f\left(w\right)\right)\left(\mathrm{mod}2\right)$. Thus, for any edge e, ${f}^{*}\left(e\right)=0$ if its two vertices have the same label and ${f}^{*}\left(e\right)=1$ if they have different labels. Let us denote ${v}_{0}$ and ${v}_{1}$ be the numbers of vertices labeled by 0 and 1 in V respectively, and let ${e}_{0}$ and ${e}_{1}$ 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 $|{v}_{0}-{v}_{1}|\le 1$ and $|{e}_{0}-{e}_{1}|\le 1$ 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 $n-1$ edges is denoted by ${P}_{n}$, and second power of fan graph has $n+1$ vertices and $3n-3$ edges is denoted by ${F}_{n}^{2}$. Let G (with ${n}_{1}$ vertices and ${m}_{1}$ edges) and H (with ${n}_{2}$ vertices and ${m}_{2}$ edges) are two graphs. The corona between G and H is the graph denoted by $G\odot H$ and is obtained by taking one copy of G and ${n}_{i}$ 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 $G\odot H$ has ${n}_{1}+{n}_{1}\cdot {n}_{2}$ vertices and ${m}_{1}+{n}_{1}\cdot {m}_{2}+{n}_{1}\cdot {n}_{2}$ edges. It is easy to see that $G\odot H$ is not in general isomorphic to $H\odot G$. A second power of a fan ${F}_{m}^{2}$ is the graph obtained from the join of the second power of a path ${P}_{m}^{2}$ and a null graph ${N}_{1}$, i.e. ${F}_{m}^{2}={P}_{m}^{2}+{N}_{1}$. So the order of ${F}_{m}^{2}$ is $m+1$ and its size is $3m-3$, in particular ${F}_{1}^{2}\equiv {P}_{2}$, ${F}_{2}^{2}\equiv {C}_{3}$ and ${F}_{3}^{2}\equiv {K}_{4}$. In this paper we study the corona ${P}_{K}\odot {F}_{m}^{2}$ and show that is cordial for all $K\ge 1$ and $m\ge 4$.

2. Terminology and Notation

We introduce some notation and terminology for a graph with 4r vertices [7] [8] [9]. Let ${M}_{r}$ denote the labeling $0101\cdots 01$, zero-one repeated r-times if r is even and $0101\cdots 010$ if r is odd; for example, ${M}_{6}=010101$ and ${M}_{5}=01010$. Welet ${{M}^{\prime }}_{2r}$ denote the labeling $1010\cdots 10$. Sometimes, we modify the labeling ${M}_{r}$ or ${{M}^{\prime }}_{r}$ by adding symbols at one end or the other (or both). We let ${L}_{4r}$ denote the labeling $0011\text{}0011\cdots 0011$ (repeated r-times) where $r\ge 1$ and, ${{L}^{\prime }}_{4r}$ denote the labeling $1100\text{}1100\cdots 1100$ (repeated r-times) where $r\ge 1$ and ${S}_{4r}$ denotes the labeling $1001\text{}1001\cdots 1001$ (repeated r-times) and ${{S}^{\prime }}_{4r}$ denotes the labeling $0110\text{}0110\cdots 0110$ (repeated r-times). In most cases, we then modify this by adding symbols at one end or the other (or both), thus ${L}_{4r}101$ denotes the labeling $0011\text{}0011\cdots 0011\text{}101$ (repeated r-times) when $r\ge 1$ and 101 when $r=0$. Similarly, $1{{L}^{\prime }}_{4r}$ is the labeling $1\text{}1100\text{}1100\cdots 1100$ (repeated r-times) when $r\ge 1$ and 1 when $r=0$. Similarly, $0{{L}^{\prime }}_{4r}1$ is the labeling $0\text{}1100\text{}1100\cdots 1100\text{}1$ when $r\ge 1$ and 01 when $r=0$. Also, we write ${0}_{r}$ for the labeling $0\cdots 0$ (repeated r-times) and ${1}_{r}$ for the labeling $1\cdots 1$ (repeated r-times) [7] [8] [9] [10]. For specific labeling L and M of $G\odot H$ where G is path and H is a second fans, we let $\left[L;M\right]$ denote the corona labeling. Additional notation that we use is the following. For a given labeling of the corona $G\odot H$, we let ${v}_{i}$ and ${e}_{i}$ (for $i=0,1$ ) be the numbers of labels that are i as before, we let ${x}_{i}$ and ${a}_{i}$ be the corresponding quantities for G, and we let ${y}_{i}$ and ${b}_{i}$ be those for H, which are connected to the vertices labeled 0 of G. Likewise, let ${{y}^{\prime }}_{i}$ and ${{b}^{\prime }}_{i}$ be those for H, which are connected to the vertices labeled 1 of G. In case it increases by one more vertexes, so ${{y}^{″}}_{i}$ and ${{b}^{″}}_{i}$ will be those for H, which are connected to the vertex labeled 1 or 0 of G. It is easy to verify that,

${v}_{0}={x}_{0}+{y}_{0}{x}_{0}+{{y}^{\prime }}_{0}\left({x}_{1}-1\right)+{{y}^{″}}_{0}$, ${v}_{1}={x}_{1}+{y}_{1}{x}_{0}+{{y}^{\prime }}_{1}\left({x}_{1}-1\right)+{{y}^{″}}_{1}$

and

${e}_{0}={a}_{0}+{b}_{0}{x}_{0}+{{b}^{\prime }}_{0}\left({x}_{1}-1\right)+{{b}^{″}}_{0}+{y}_{0}{x}_{0}+{{y}^{\prime }}_{1}\left({x}_{1}-1\right)+{{y}^{″}}_{0}$,

${e}_{1}={a}_{1}+{b}_{1}{x}_{0}+{{b}^{\prime }}_{1}\left({x}_{1}-1\right)+{{b}^{″}}_{1}+{y}_{1}{x}_{0}+{{y}^{\prime }}_{0}\left({x}_{1}-1\right)+{{y}^{″}}_{1}$.

Thus,

${v}_{0}–{v}_{1}=\left({x}_{0}–{x}_{1}\right)+{x}_{0}\left({y}_{0}–{y}_{1}\right)+\left({x}_{1}-1\right)\left({{y}^{\prime }}_{0}-{{y}^{\prime }}_{1}\right)+\left({{y}^{″}}_{0}-{{y}^{″}}_{1}\right)$

and

$\begin{array}{l}{e}_{0}–{e}_{1}=\left({a}_{0}–{a}_{1}\right)+{x}_{0}\left({b}_{0}–{b}_{1}\right)+\left({x}_{1}-1\right)\left({{b}^{\prime }}_{0}-{{b}^{\prime }}_{1}\right)+\left({{b}^{″}}_{0}-{{b}^{″}}_{1}\right)\\ \text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}+{x}_{0}\left({y}_{0}–{y}_{1}\right)-\left({x}_{1}-1\right)\left({{y}^{\prime }}_{0}-{{y}^{\prime }}_{1}\right)-\left({{y}^{″}}_{1}-{{y}^{″}}_{0}\right)\end{array}$

when it comes to the proof, we only need to show that, for each specified combination of labeling, $|{v}_{0}-{v}_{1}|\le 1$ and $|{e}_{0}-{e}_{1}|\le 1$.

3. The Corona between Paths and Second Fans

In this section, we show that the corona between paths and second power of Fan graphs ${P}_{K}\odot {F}_{m}^{2}$ is cordial for all $k\ge 1$, and $m\ge 4$. This target will be achieved after the following series of lemmas.

Lemma 3.1 ${P}_{K}\odot {F}_{m}^{2}$ is cordial for all $k\ge 1$ and $m\equiv 0\left(\mathrm{mod}4\right)$.

Proof. We need to examine the following cases:

Case (1). $k\equiv 0\left(\mathrm{mod}4\right)$.

Let $k=4r$, $r\ge 1$. Then, one can choose the labeling $\left[{L}_{4r}:0{{M}^{\prime }}_{4s},0{{M}^{\prime }}_{4s},1{M}_{4s},1{M}_{4s},\cdots \left(r\text{-times}\right)\right]$ for ${P}_{4r}\odot {F}_{4s}^{2}$. Therefore , ${x}_{0}={x}_{1}=2r{a}_{0}=2r$, ${a}_{1}=2r-1$, ${y}_{0}=2s+1$, ${y}_{1}=2s$, ${b}_{0}=6s-2$, ${b}_{1}=6s-1$, ${{y}^{\prime }}_{0}=2s$, ${{y}^{\prime }}_{1}=2s+1$, ${{b}^{\prime }}_{0}=6s-2$ and ${{b}^{\prime }}_{1}=6s-1$. Hence, one can easily show that ${v}_{0}-{v}_{1}=0$ and ${e}_{0}-{e}_{1}=1$ Thus ${P}_{4r}\odot {F}_{4s}^{2}$, $s\ge 1$ is cordial.

As an example, Figure 1 illustrates ${P}_{4}\odot {F}_{4}^{2}$.

Figure 1. The corona between paths and second power of Fan graphs ${P}_{4}\odot {F}_{4}^{2}$.

Case (2). $k\equiv 1\left(\mathrm{mod}4\right)$.

Let $k=4r+1$, $r>0$. Then, one can choose the labelling $\left[{L}_{4r}\text{\hspace{0.17em}}1:0{M}_{4s},0{M}_{4s},1{M}_{4s},1{M}_{4s},\cdots \left(r\text{-times}\right),0{M}_{4s}\right]$ for ${P}_{4r+1}\odot {F}_{4s}^{2}$. Therefore ${x}_{0}=2r$, ${x}_{1}={a}_{0}=2r+1$, ${a}_{1}=2r-1$, ${y}_{0}=2s+1$, ${y}_{1}=2s$, ${b}_{0}=6s-2$, ${b}_{1}=6s-1$, ${{y}^{\prime }}_{0}=2s$, ${{y}^{\prime }}_{1}=2s+1$, ${{b}^{\prime }}_{0}=6s-2$, ${{b}^{\prime }}_{1}=6s-1$, ${{y}^{″}}_{0}=2s+1$, ${{y}^{″}}_{1}=2s$, ${{b}^{″}}_{0}=6s-2$ and ${{b}^{″}}_{1}=6s-1$. Hence, one can easily show that ${v}_{0}-{v}_{1}=0$ and ${e}_{0}-{e}_{1}=0$. Thus ${P}_{4r+1}\odot {F}_{4s}^{2},s\ge 1$ is cordial.

As an example, Figure 2 illustrates ${P}_{5}\odot {F}_{4}^{2}$.

Figure 2. The corona between paths and second power of Fan graphs ${P}_{5}\odot {F}_{4}^{2}$.

Case (3). $k\equiv 2\left(\mathrm{mod}4\right)$.

Let $k=4r+2$, $r>0$. Then, one can choose the labelling $\left[{L}_{4r}\text{\hspace{0.17em}}10:0{{M}^{\prime }}_{4s},0{{M}^{\prime }}_{4s},1{M}_{4s},1{M}_{4s},\cdots \left(r\text{-times}\right),1{M}_{4s},0{{M}^{\prime }}_{4s}\right]$ for ${P}_{4r+2}\odot {F}_{4s}$. Therefore ${x}_{0}={x}_{1}=2r+1$, ${a}_{0}=2r+1$, ${a}_{1}=2r$, ${y}_{0}=2s+1$, ${y}_{1}=2s$, ${b}_{0}=6s-2$, ${b}_{1}=6s-1$, ${{y}^{\prime }}_{0}=2s$, ${{y}^{\prime }}_{1}=2s+1$, ${{b}^{\prime }}_{0}=6s-2$ and ${{b}^{\prime }}_{1}=6s-1$. Hence, one can easily show that ${v}_{0}-{v}_{1}=0$ and ${e}_{0}-{e}_{1}=1$. Thus ${P}_{4r+2}\odot {F}_{4s}^{2}$, $s\ge 1$ is cordial.

As an example, Figure 3 illustrates ${P}_{6}\odot {F}_{4}^{2}$.

Figure 3. The corona between paths and second power of Fan graphs ${P}_{6}\odot {F}_{4}^{2}$.

Case (4). $k\equiv 3\left(\mathrm{mod}4\right)$.

Let $k=4r+3$, $r>0$. Then, one can choose the labelling $\left[{L}_{4r}\text{\hspace{0.17em}}110:0{{M}^{\prime }}_{4s},0{{M}^{\prime }}_{4s},1{{M}^{\prime }}_{4s},1{{M}^{\prime }}_{4s},\cdots \left(r\text{-times}\right),1{{M}^{\prime }}_{4s},1{M}_{4s},0{{M}^{\prime }}_{4s}\right]$ for ${P}_{4r+3}\odot {F}_{4s}^{2}$. Therefore, ${x}_{0}=2r+1$, ${x}_{1}={a}_{0}=2r+2$, ${a}_{1}=2r$, ${y}_{0}=2s+1$, ${y}_{1}=2s$, ${b}_{0}=6s-2$, ${b}_{1}=6s-1$, ${{y}^{\prime }}_{0}=2s$, ${{y}^{\prime }}_{1}=2s+1$, ${{b}^{\prime }}_{0}=6s-2$, ${{b}^{\prime }}_{1}=6s-1$, ${{y}^{″}}_{0}=2s+1$, ${{y}^{″}}_{1}=2s$, ${{b}^{″}}_{0}=6s-2$ and ${{b}^{″}}_{1}=6s-1$. Hence, one can easily show that ${v}_{0}-{v}_{1}=0$ and ${e}_{0}-{e}_{1}=0$. Thus ${P}_{4r+3}\odot {F}_{4s}^{2},s\ge 1$ is cordial.

As example, Figure 4 illustrates ${P}_{7}\odot {F}_{4}^{2}$.

Figure 4. The corona between paths and second power of Fan graphs ${P}_{7}\odot {F}_{4}^{2}$.

Lemma 3.2 ${P}_{K}\odot {F}_{m}^{2}$ is cordial for all $k\ge 1$ and $m\equiv 1\left(\mathrm{mod}4\right)$.

Proof. We need to examine the following cases:

Case (1). $k\equiv 0\left(\mathrm{mod}4\right)$.

Let $k=4r$, $r\ge 1$. Then, one can choose the labeling $\left[{L}_{4r}:{11}_{3}{0}_{2}{M}_{4s-4},{11}_{3}{0}_{2}{M}_{4s-4},{00}_{3}{1}_{2}{{M}^{\prime }}_{4s-4},{00}_{3}{1}_{2}{{M}^{\prime }}_{4s-4},\cdots \left(r\text{-times}\right)\right]$ for ${P}_{4r}\odot {F}_{4s+1}^{2}$. Therefore ${x}_{0}={x}_{1}={a}_{0}=2r$, ${a}_{1}=2r-1$, ${y}_{0}=2s$, ${y}_{1}=2s+2$, ${b}_{0}=6s+1$, ${b}_{1}=6s-1$, ${{y}^{\prime }}_{0}=2s+2$, ${{y}^{\prime }}_{1}=2s$ and ${{b}^{\prime }}_{0}=6s+1$, ${{b}^{\prime }}_{1}=6s-1$. Hence, one can easily show that ${v}_{0}-{v}_{1}=0$ and ${e}_{0}-{e}_{1}=1$. Thus ${P}_{4r}\odot {F}_{4s+1}^{2}$, $s\ge 1$ is cordial.

As an example, Figure 5 illustrates ${P}_{4}\odot {F}_{5}^{2}$.

Figure 5. The corona between paths and second power of Fan graphs ${P}_{4}\odot {F}_{5}^{2}$.

Case (2). $k\equiv 1\left(\mathrm{mod}4\right)$.

Let $k=4r+1$, $r>0$. Then, one can choose the labeling $\left[{L}_{4r}\text{\hspace{0.17em}}0:{11}_{3}{0}_{2}{M}_{4s-4},{11}_{3}{0}_{2}{M}_{4s-4},{00}_{3}{1}_{2}{{M}^{\prime }}_{4s-4},{00}_{3}{1}_{2}{{M}^{\prime }}_{4s-4},\cdots \left(r\text{-times}\right),{10}_{3}{1}_{2}{M}_{4s-4}\right]$ for ${P}_{4r+1}\odot {F}_{4s+1}^{2}$. Therefore ${x}_{0}=2r+1$, ${x}_{1}={a}_{0}={a}_{1}=2r$, ${y}_{0}=2s+2$, ${y}_{1}=2s$, ${b}_{0}=6s-1$, ${b}_{1}=6s+1$, ${{y}^{\prime }}_{0}=2s$, ${{y}^{\prime }}_{1}=2s+2$, ${{b}^{\prime }}_{0}=6s-1$, ${{b}^{\prime }}_{1}=6s+1$, ${{y}^{″}}_{0}={{y}^{″}}_{1}=2s+1$, and ${{b}^{″}}_{0}={{b}^{″}}_{1}=6s$. Hence, one can easily show that ${v}_{0}-{v}_{1}=1$ and ${e}_{0}-{e}_{1}=0$. Thus ${P}_{4r+1}\odot {F}_{4s+1}^{2}$, $s\ge 1$, is cordial.

As an example, Figure 6 illustrates ${P}_{5}\odot {F}_{5}^{2}$.

Figure 6. The corona between paths and second power of Fan graphs ${P}_{5}\odot {F}_{5}^{2}$.

Case (3). $k\equiv 2\left(\mathrm{mod}4\right)$.

Let $k=4r+2$, $r\ge 0$. Then, one can choose the labeling [ ${L}_{4r}\text{\hspace{0.17em}}10:{11}_{3}{0}_{2}{M}_{4s-4}$, ${11}_{3}{0}_{2}{M}_{4s-4}$, ${00}_{3}{1}_{2}{{M}^{\prime }}_{4s-4}$, ${00}_{3}{1}_{2}{{M}^{\prime }}_{4s-4}$, $\cdots \left(r\text{-times}\right)$, ${00}_{3}{1}_{2}{{M}^{\prime }}_{4s-4}$, ${11}_{3}{0}_{2}{M}_{4s-4}$ ] for ${P}_{4r+2}\odot {F}_{4s+1}^{2}$. Therefore ${x}_{0}={x}_{1}={a}_{0}=2r+1$, ${a}_{1}=2r$, ${y}_{0}=2s+2$, ${y}_{1}=2s$, ${b}_{0}=6s-1$, ${b}_{1}=6s+1$, ${{y}^{\prime }}_{0}=2s$, ${{y}^{\prime }}_{1}=2s+2$ and ${{b}^{\prime }}_{0}=6s-1$, ${{b}^{\prime }}_{1}=6s+1$. Hence one can easily show that ${v}_{0}-{v}_{1}=0$ and ${e}_{0}-{e}_{1}=1$. Thus ${P}_{4r+2}\odot {F}_{4s+1}^{2}$, $s\ge 1$, is cordial.

As an example, Figure 7 illustrates ${P}_{6}\odot {F}_{5}^{2}$.

Figure 7. The corona between paths and second power of Fan graphs ${P}_{6}\odot {F}_{5}^{2}$.

Case (4). $k\equiv 3\left(\mathrm{mod}4\right)$.

Let $k=4r+3$, $r\ge 0$. Then, one can choose the labeling [ ${L}_{4r}\text{\hspace{0.17em}}101:{11}_{3}{0}_{2}{M}_{4s-4}$, ${11}_{3}{0}_{2}{M}_{4s-4}$, ${00}_{3}{1}_{2}{{M}^{\prime }}_{4s-4}$, ${00}_{3}{1}_{2}{{M}^{\prime }}_{4s-4}$, $\cdots \left(r\text{-times}\right)$, ${00}_{3}{1}_{2}{{M}^{\prime }}_{4s-4}$, ${11}_{3}{0}_{2}{M}_{4s-4}$, ${00}_{2}{1}_{3}{{M}^{\prime }}_{4s-4}$ ] for ${P}_{4r+3}\odot {F}_{4s+1}^{2}$. Therefore ${x}_{0}={a}_{0}={a}_{1}=2r+1$, ${x}_{1}=2r+2$, ${y}_{0}=2s$, ${y}_{1}=2s+2$, ${b}_{0}=6s+1$, ${b}_{1}=6s-1$, ${{y}^{\prime }}_{0}=2s+2$, ${{y}^{\prime }}_{1}=2s$, ${{b}^{\prime }}_{0}=6s+1$, ${{b}^{\prime }}_{1}=6s-1$, ${{y}^{″}}_{0}={{y}^{″}}_{1}=2s+1$, and ${{b}^{″}}_{0}={{b}^{″}}_{1}=6s$. Hence, one can easily show that ${v}_{0}-{v}_{1}=-1$ and ${e}_{0}-{e}_{1}=0$. Thus ${P}_{4r+3}\odot {F}_{4s+1}^{2}$, $s\ge 1$, is cordial.

As an example, Figure 8 illustrates ${P}_{7}\odot {F}_{5}^{2}$.

Figure 8. The corona between paths and second power of Fan graphs ${P}_{7}\odot {F}_{5}^{2}$.

Lemma 3.3 ${P}_{k}\odot {F}_{m}^{2}$ is cordial for all $k\ge 1$ and $m\equiv 2\left(\mathrm{mod}4\right)$.

Proof. We need to study the following cases:

Case (1). $k\equiv 0\left(\mathrm{mod}4\right)$.

Let $k=4r$, $r\ge 1$. Then, one can choose the labeling $\left[{L}_{4r}:0{{M}^{\prime }}_{4s+2},0{{M}^{\prime }}_{4s+2},1{M}_{4s+2},1{M}_{4s+2},\cdots \left(r\text{-times}\right)\right]$ for ${P}_{4r}\odot {F}_{4s+1}^{2}$. Therefore ${x}_{0}={x}_{1}={a}_{0}=2r$, ${a}_{1}=2r-1$, ${y}_{0}=2s+2$, ${y}_{1}=2s+1$, ${b}_{0}=6s+1$, ${b}_{1}=6s+2$, ${{y}^{\prime }}_{0}=2s+1$, ${{y}^{\prime }}_{1}=2s+2$, ${{b}^{\prime }}_{0}=6s+1$ and ${{b}^{\prime }}_{1}=6s+2$. Hence, one can easily show that ${v}_{0}-{v}_{1}=0$ and ${e}_{0}-{e}_{1}=1$. Thus ${P}_{4r}\odot {F}_{4s+1}^{2},s\ge 1$ is cordial.

As an example, Figure 9 illustrates ${P}_{4}\odot {F}_{6}^{2}$.

Figure 9. The corona between paths and second power of Fan graphs ${P}_{4}\odot {F}_{6}^{2}$.

Case (2). $k\equiv 1\left(\mathrm{mod}4\right)$.

Let $k=4r+1$, $r\ge 0$. Then, one can choose the labeling $\left[{L}_{4r}\text{\hspace{0.17em}}1:0{{M}^{\prime }}_{4s+2},0{{M}^{\prime }}_{4s+2},1{{M}^{\prime }}_{4s+2},1{{M}^{\prime }}_{4s+2},\cdots \left(r\text{-times}\right),0{M}_{4s+2}\right]$ for ${P}_{4r+1}\odot {F}_{4s+2}^{2}$. Therefore ${x}_{0}=2r$, ${x}_{1}={a}_{0}=2r+1$, ${a}_{1}=2r-1$, ${y}_{0}=2s+2$, ${y}_{1}=2s+1$, ${b}_{0}=6s+1$, ${b}_{1}=6s+2$, ${{y}^{\prime }}_{0}=2s+1$, ${{y}^{\prime }}_{1}=2s+2$, ${{b}^{\prime }}_{0}=6s+1$, ${{b}^{\prime }}_{1}=6s+2$, ${{y}^{″}}_{0}=2s+2$, ${{y}^{″}}_{1}=2s+1$, ${{b}^{″}}_{0}=6s+1$ and ${{b}^{″}}_{1}=6s+2$. Hence, one can easily show that ${v}_{0}-{v}_{1}=0$ and ${e}_{0}-{e}_{1}=0$. Thus ${P}_{4r+1}\odot {F}_{4s+2}^{2}$, $s\ge 1$ is cordial.

As an example, Figure 10 illustrates ${P}_{5}\odot {F}_{6}^{2}$.

Figure 10. The corona between paths and second power of Fan graphs ${P}_{5}\odot {F}_{6}^{2}$.

Case (3). $k\equiv 2\left(\mathrm{mod}4\right)$.

Let $k=4r+2$, $r\ge 0$. Then, one can choose the labeling $\left[{L}_{4r}\text{\hspace{0.17em}}10:0{{M}^{\prime }}_{4s+2},0{{M}^{\prime }}_{4s+2},1{M}_{4s+2},1{M}_{4s+2},\cdots \left(r\text{-times}\right),1{M}_{4s+2},0{{M}^{\prime }}_{4s+2}\right]$ for ${P}_{4r+2}\odot {F}_{4s+2}^{2}$. Therefore ${x}_{0}={x}_{1}={a}_{0}=2r+1$, ${a}_{1}=2r$, ${y}_{0}=2s+2$, ${y}_{1}=2s+1$, ${b}_{0}=6s+1$, ${b}_{1}=6s+2$, ${{y}^{\prime }}_{0}=2s+1$, ${{y}^{\prime }}_{1}=2s+2$, ${{b}^{\prime }}_{0}=6s+1$ and ${{b}^{\prime }}_{1}=6s+2$. Hence, one can easily show that ${v}_{0}-{v}_{1}=0$ and ${e}_{0}-{e}_{1}=1$. Thus ${P}_{4r+2}\odot {F}_{4s+2}^{2}$, $s\ge 1$ is cordial.

As an example, Figure 11 illustrates ${P}_{6}\odot {F}_{6}^{2}$.

Figure 11. The corona between paths and second power of Fan graphs ${P}_{6}\odot {F}_{6}^{2}$.

Case (4). $k\equiv 3\left(\mathrm{mod}4\right)$.

Let $k=4r+3$, $r\ge 0$. Then, one can choose the labeling $\left[{L}_{4r}\text{ }\text{ }110:0{{M}^{\prime }}_{4s+2},0{{M}^{\prime }}_{4s+2},1{M}_{4s+2},1{M}_{4s+2},\cdots \left(r\text{-times}\right),1{M}_{4s+2},{00}_{2}{1}_{2}{{M}^{\prime }}_{4s-2},0{{M}^{\prime }}_{4s+2}\right]$ for ${P}_{4r+3}\odot {F}_{4s+2}^{2}$. Therefore ${x}_{0}=2r+1$, ${x}_{1}={a}_{0}=2r+2$, ${y}_{0}=2s+2$, ${a}_{1}=2r$, ${y}_{0}=2s+2$, ${y}_{1}=2s+1$, ${b}_{0}=6s+1$, ${b}_{1}=6s+2$, ${{y}^{\prime }}_{0}=2s+1$, ${{y}^{\prime }}_{1}=2s+2$, ${{b}^{\prime }}_{0}=6s+1$, ${{b}^{\prime }}_{1}=6s+2$, ${{y}^{″}}_{0}=2s+2$, ${{y}^{″}}_{1}=2s+1$, ${{b}^{″}}_{0}=6s+1$ and ${{b}^{″}}_{1}=6s+2$. Hence, one can easily show that ${v}_{0}-{v}_{1}=0$ and ${e}_{0}-{e}_{1}=0$. Thus ${P}_{4r+3}\odot {F}_{4s+2}^{2}$, $s\ge 1$ is cordial.

As an example, Figure 12 illustrates ${P}_{7}\odot {F}_{6}^{2}$.

Figure 12. The corona between paths and second power of Fan graphs ${P}_{7}\odot {F}_{6}^{2}$.

Lemma 3.4 ${P}_{k}\odot {F}_{m}^{2}$ is cordial for all $k\ge 1$ and $m\equiv 3\left(\mathrm{mod}4\right)$.

Proof: Will be examined following cases:

Case (1). $k\equiv 0\left(\mathrm{mod}4\right)$.

Let $k=4r$, $r\ge 1$. Then, one can choose the labeling $\left[{L}_{4r}:{10}_{3}{{M}^{\prime }}_{4s},{10}_{3}{{M}^{\prime }}_{4s},{101}_{2}{M}_{4s},{101}_{2}{M}_{4s},\cdots \left(r\text{-times}\right)\right]$ for ${P}_{4r}\odot {F}_{4s+3}^{2}$. Therefore ${x}_{0}={x}_{1}={a}_{0}=2r$, ${a}_{1}=2r-1$, ${y}_{0}=2s+3$, ${y}_{1}=2s+1$, ${b}_{0}=6s+2$, ${b}_{1}=6s+4$, ${{y}^{\prime }}_{0}=2s+1$, ${{y}^{\prime }}_{1}=2s+3$ and ${{b}^{\prime }}_{0}=6s+2$, ${{b}^{\prime }}_{1}=6s+4$. Hence, one can easily show that ${v}_{0}-{v}_{1}=0$ and ${e}_{0}-{e}_{1}=1$. Thus ${P}_{4r}\odot {F}_{4s+3}^{2}$, $s\ge 1$ is cordial.

As an example, Figure 13 illustrates ${P}_{4}\odot {F}_{7}^{2}$.

Figure 13. The corona between paths and second power of Fan graphs ${P}_{4}\odot {F}_{7}^{2}$.

Case (2). $k\equiv 1\left(\mathrm{mod}4\right)$.

Let $k=4r+1$, $r\ge 0$. Then, one can choose the labeling $\left[{L}_{4r}\text{\hspace{0.17em}}1:{10}_{3}{{M}^{\prime }}_{4s},{10}_{3}{{M}^{\prime }}_{4s},{101}_{2}{M}_{4s},{101}_{2}{M}_{4s},\cdots \left(r\text{-times}\right),{01}_{2}0{{M}^{\prime }}_{4s}\right]$ for ${P}_{4r+1}\odot {F}_{4s+3}^{2}$. Therefore ${x}_{0}=2r$, ${x}_{1}={a}_{0}=2r+1$, ${a}_{1}=2r-1$, ${y}_{0}=2s+3$, ${y}_{1}=2s+1$, ${b}_{0}=6s+2$, ${b}_{1}=6s+4$, ${{y}^{\prime }}_{0}=2s+1$, ${{y}^{\prime }}_{1}=2s+3$, ${{b}^{\prime }}_{0}=6s+2$, ${{b}^{\prime }}_{1}=6s+4$, ${{y}^{″}}_{0}={{y}^{″}}_{1}=2s+2$, ${{b}^{″}}_{0}=6s+2$ and ${{b}^{″}}_{1}=6s+4$. Hence one can easily show that ${v}_{0}-{v}_{1}=-1$ and ${e}_{0}-{e}_{1}=0$. Thus ${P}_{4r+1}\odot {F}_{4s+3}^{2}$, $s\ge 1$ is cordial.

As an example, Figure 14 illustrates ${P}_{5}\odot {F}_{7}^{2}$.

Figure 14. The corona between paths and second power of Fan graphs ${P}_{5}\odot {F}_{7}^{2}$.

Case (3). $k\equiv 2\left(\mathrm{mod}4\right)$.

Let $k=4r+2$, $r\ge 0$. Then, one can choose the labeling $\left[{L}_{4r}\text{\hspace{0.17em}}10:{10}_{3}{{M}^{\prime }}_{4s},{10}_{3}{{M}^{\prime }}_{4s},{101}_{2}{M}_{4s},{101}_{2}{M}_{4s},\cdots \left(r\text{-times}\right),{101}_{2}{M}_{4s},{10}_{3}{{M}^{\prime }}_{4s}\right]$ for ${P}_{4r+2}\odot {F}_{4s+3}^{2}$. Therefore ${x}_{0}={x}_{1}={a}_{0}=2r+1$, ${a}_{1}=2r$, ${y}_{0}=2s+3$, ${y}_{1}=2s+1$, ${b}_{0}=6s+2$, ${b}_{1}=6s+4$, ${{y}^{\prime }}_{0}=2s+1$, ${{y}^{\prime }}_{1}=2s+3$, ${{b}^{\prime }}_{0}=6s+2$ and ${{b}^{\prime }}_{1}=6s+4$. Hence, one can easily show that ${v}_{0}-{v}_{1}=0$ and ${e}_{0}-{e}_{1}=1$. Thus ${P}_{4r+2}\odot {F}_{4s+3}^{2}$, $s\ge 1$ is cordial.

As an example, Figure 15 illustrates ${P}_{6}\odot {F}_{7}^{2}$.

Figure 15. The corona between paths and second power of Fan graphs ${P}_{6}\odot {F}_{7}^{2}$.

Case (4). $k\equiv 3\left(\mathrm{mod}4\right)$.

Let $k=4r+3$, $r\ge 0$. Then, one can choose the labeling [ ${L}_{4r}\text{\hspace{0.17em}}100:{10}_{3}{{M}^{\prime }}_{4s}$, ${10}_{3}{{M}^{\prime }}_{4s}$, ${101}_{2}{M}_{4s}$, ${101}_{2}{M}_{4s}$, $\cdots \left(r\text{-times}\right)$, ${101}_{2}{M}_{4s}$, ${10}_{3}{{M}^{\prime }}_{4s}$, ${01}_{2}0{{M}^{\prime }}_{4s}$ ] for ${P}_{4r+3}\odot {F}_{4s+3}^{2}$. Therefore ${x}_{0}={a}_{0}=2r+2$, ${x}_{1}=2r+1$, ${a}_{1}=2r$, ${y}_{0}=2s+3$, ${y}_{1}=2s+1$, ${b}_{0}=6s+2$, ${b}_{1}=6s+4$, ${{y}^{\prime }}_{0}=2s+1$, ${{y}^{\prime }}_{1}=2s+3$, ${{b}^{\prime }}_{0}=6s+2$, ${{b}^{\prime }}_{1}=6s+4$, ${{y}^{″}}_{0}={{y}^{″}}_{1}=2s+2$, ${{b}^{″}}_{0}=6s+2$ and ${{b}^{″}}_{1}=6s+4$. Hence one can easily show that ${v}_{0}-{v}_{1}=1$ and ${e}_{0}-{e}_{1}=0$. Thus ${P}_{4r+3}\odot {F}_{4s+3}^{2}$, $s\ge 1$ is cordial.

As an example, Figure 16 illustrates ${P}_{7}\odot {F}_{7}^{2}$.

Figure 16. The corona between paths and second power of Fan graphs ${P}_{7}\odot {F}_{7}^{2}$.

As a consequence of all previous lemmas one can establish the following theorem.

Theorem. The corona between path ${P}_{k}$ & ${F}_{m}^{2}$ is cordial for all k and m.

Cite this paper: Elrokh, A. , Nada, S. and El-Shafey, E. (2021) Cordial Labeling of Corona Product of Path Graph and Second Power of Fan Graph. Open Journal of Discrete Mathematics, 11, 31-42. doi: 10.4236/ojdm.2021.112003.
References

[1]   Gallian, J.A. (2010) A Dynamic Survey of Graph Labeling. The Electronic Journal of Combinatorics, 17, DS6.
http://www.combinatorics.org/Surveys/ds6.pdf

[2]   Golomb, S.W. (1972) How to Number a Graph. In: Read, R.C. Ed., Graph Theory and Computing, Academic Press, New York, 23-37.
https://doi.org/10.1016/B978-1-4832-3187-7.50008-8

[3]   Graham, R.L. and Sloane, N.J.A. (1980) On Additive Bases and Harmonious Graphs. SIAM Journal on Algebraic Discrete Methods, 1, 382-404
https://doi.org/10.1137/0601045

[4]   Rosa, A. (1967) On Certain Valuations of the Vertices of a Graph. Theory of Graphs (International Symposium, Rome, July 1966), Dunod Gordon & Breach Science Publishers, Inc., New York and Dunod Paris, 349-355.

[5]   Cahit, I. (1987) Cordial Graphs: A Weaker Version of Graceful and Harmonious Graphs. Ars Combinatoria, 23, 201-207.

[6]   Cahit, I. (1990) On Cordial and 3-Equitable Labeling of Graphs. Utilitas Mathematica, 37, 189-198.

[7]   Diab, A.T. (2011) On Cordial Labeling of Wheels with Other Graphs. Ars Combinatoria, 100, 265-279.

[8]   Diab, A.T. (2010) On Cordial Labeling of the Second Power of Paths with Other Graphs, Ars Combinatoria, 97A, 327-343.

[9]   Diab, A.T. (2011) Generalization of Some Result of Cordial Graphs. Ars Combinatoria, 99, 161-173.

[10]   Azaizeh, A., Hasni, R., Ahmad, A. and Lau, G.-C. (2015) 3-Total Edge Product Cordial Labeling of Graphs, Far East Journal of Mathematical Sciences, 96, 193-209.
https://doi.org/10.17654/FJMSJan2015_193_209

Top