Some Results on Cordial Digraphs

Mohammed M. Ali Al-Shamiri^1,2, Shokry I. Nada³, Ashraf I. Elrokh³, Yasser Elmshtaye¹

¹Department of Mathematics, Faculty of Science and Arts, Mohayel Assir, King Khalid University, Abha, KSA.
²Department of Mathematics and Computer, Faculty of Science, Ibb University, Ibb, Yemen.
³Department of Mathematics, Faculty of Science, Munofia University, Monofia, Egypt.

DOI: 10.4236/ojdm.2020.101002                

Abstract

A digraph is a graph in which each edge has an orientation. A linear directed path, , is a path whose all edges have the same orientation. A linear simple graph is called directed cordial if it admits 0 - 1 labeling that satisfies certain condition. In this paper, we study the cordiality of directed paths  and their second power . Similar studies are done for  and the join  . We show that ,  and  are directed cordial. Sufficient conditions are given to the join   to be directed cordial.

Keywords

Paths, Second Power of Path, Join of Paths, Cordial Graph

1. Introduction

One of the major problems concerning graph labeling is the cordialities of graphs. It is related to many applications in computer science and communication network. An excellent reference on this subject in the survey is by Gallian [1] and Harary [2]. A path $P_n=a_0{a}_1\cdots a_{n-1}$ is an alternating sequence of distinct vertices and $n-1$ edges. $P_n$ is said to be linearly directed if all its edges have the same direction: clockwise or counterclockwise. The distance $d\left(x,y\right)$ between two vertices $x,y$ in V of a graph $G=\left(V,E\right)$ is the length of shortest path joining them in G. The second power of a path $P_n$, denoted $P_n^2$, is the union of $P_n$ and the set of all edges $a_i{a}_j$ with distance 2 and $i<j$. In Particular $P_2^2\cong C_2$, $P_3^2\cong C_3$ [3]. The origin concept of cordial graphs is due to Cahit [4]. In 1990, Cahit [5] proved the following: each tree is cordial; a complete graph $K_n$ is cordial if and only if $n\le 3$ and a complete bipartite graph $K_{n,m}$ is cordial for all positive integers n and m. In this paper, we only deal with linearly directed paths and their second power together with the union and join of directed paths. Let $G=P_n$ be a digraph and let $f:V\to \left\{0,1\right\}$ be a labeling of its vertices and its set of edges, and let $P_n$ be linearly directed (see Figure 1).

We define the edge labeling as follows $f^{*}:E\to \left\{0,1\right\}$

$f^{*}\left(v_i{v}_{i+1}\right)=2^{v_i}\left(\mathrm{mod}2\right)$

Let $v_0$ and $v_1$ be the numbers of vertices that are labeled by 0 and 1, respectively, in G and let $e_0$ and $e_1$ be the corresponding numbers of edges. Such a labeling is called cordial if both $\left|v_0-v_1\right|\le 1$ and $\left|e_0-e_1\right|\le 1$ holds [4]. A graph is called cordial if it admits a cordial labeling [2]. If a linearly directed path is cordial, we call it a directed cordial path. The directed second power of a path is a linearly directed path with the added edges in $P_n^2$ that are endowed with directions defined as follows: $a_i{a}_{i+1},a_{i+1}{a}_{i+2}$ and $a_{i+2}{a}_i$ have the same orientation (see Figure 2).

Given two disjoint paths $P_n$ and $P_m$, then their union, $P_n\cup P_m$, is simply the unions of their sets of vertices and edges. If $x_i$ and $a_i$ represent the numbers of vertices and edges that are labeled i in $P_n$, respectively, and the corresponding quantities for $P_m$ are $y_i$ and $b_i$. Therefore, it is obvious that $v_0-v_1=\left(x_0-x_1\right)+\left(y_0-y_1\right)$ and $e_0-e_1=\left(a_0-a_1\right)+\left(b_0-b_1\right)$.

The join (sum) $P_n+P_m$ is obtained from $P_n\cup P_m$ by adding all edges that join each vertex of $P_n$ to all vertices of $P_m$. Consider $P_n$ and $P_m$ have the same orientation. Then, we define the direction of all new edges that are connecting vertices of $P_n$ and $P_m$ to be from vertices of $P_n$ to vertices of $P_m$. It follows that $\left|v_0-v_1\right|=\left|\left(x_0-x_1\right)+\left(y_0-y_1\right)\right|$, and $\left|e_0-e_1\right|=\left|\left(a_0-a_1\right)+\left(b_0-b_1\right)-m\left(x_0-x_1\right)\right|$.

We shall show that $P_n,P_n^2$ and $P_n\cup P_m$ are directed cordial for all positive integers n, m. Some sufficient conditions are given to make the join $P_n+P_m$ is directed cordial. It is worth noting that, although $K_4=P_2+P_2$ is directed cordial but according to Cahit [5], it is not cordial.

Figure 1. Linearly Directed Path.

Figure 2. The Directed Second Power of a Path Have The Same Orientation.

2. Terminology and Notation

Let $M_{2r}$ denote the labeling $01\cdots 01$ (r times), and the labeling $01\cdots 010$ is denoted by $M_{2r+1}$. We let ${M^{\prime }}_{2r}$ denote the labeling $10\cdots 10$. Let $L_{4r}$ denote the labeling $0011\cdots 0011$ (r-times) and ${L^{\prime }}_{4r}$ denote the labeling $1100\cdots 1100$ (r-times), where $r\ge 1$. The labeling $0\cdots 0$ (r-times) is denoted by $0_r$. Similarly, $1\cdots 1$ (r-times) is denoted by $1_r$. We can modify this by adding symbols at one end or the other (or both), thus $L_{4r}101$ denotes the labeling $0011\cdots 0011101$, when $r\ge 1$ and 101 when $r=0$. Similarly, $0{L^{\prime }}_{4r}1$ is the labeling $01100\cdots 11001$ when $r\ge 1$ and 01 when $r=0$.

3. Directed Cordial Paths

Let $G=\left(V,E\right)$ be a graph where G is linearly directed path. We show that each linearly directed path is directed cordial.

Lemma 3.1.

The directed path $P_m$, is directed cordial; $m\ge 2$.

Proof: Let us first examine the particular cases $P_2$ and $P_3$.

For $P_2$, we choose the labeling 01; therefore $x_0=x_1=1,a_0=0,a_1=1$. Without any loss of generality, one may use the clockwise direction and hence $\left|v_0-v_1\right|=0$, and, $\left|e_0-e_1\right|=1$. So $P_2$ is directed cordial.

For $P_3$, we choose the labeling 010; therefore $x_0=2,x_1=1$, and $a_0=a_1=1$, also we may consider the direction of $P_3$ as done in $P_2$ ; hence $\left|v_0-v_1\right|=1$ and $\left|e_0-e_1\right|=0$, so $P_3$ is directed cordial (Figure 3).

To complete the proof, we need to study the following four cases:

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

Suppose that $m=4r,r\ge 1$. We choose the labeling, $L_{4r}$ for $P_{4r}$. Therefore $x_0=x_1=2r$, $a_0=2r-1$, and $a_1=2r$. Consequently, $\left|v_0-v_1\right|=0$ and, $\left|e_0-e_1\right|=1$. Thus $P_{4r}$ is directed cordial. Figure 4 illustrates the directed cordial path $P_8$.

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

Suppose that $m=4r+1,r\ge 1$. Then, one can choose the labeling, $L_{4s}0$ for $P_{2r+1}$. Therefore $x_0=2r+1,x_1=2r$, and $a_0=a_1=2r$. Consequently, $\left|v_0-v_1\right|=1$ and, $\left|e_0-e_1\right|=0$. Thus $P_{4r+1}$ is directed cordial. Figure 5 illustrates the directed cordial path $P_5$.

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

Suppose that $m=4r+2;r\ge 1$. Then, one can choose the labeling, $M_{2r}$ for $P_{4r+2}$. Therefore, $x_0=x_1=2r$, $a_0=2r-1$, and $a_1=2r$. Consequently, $\left|v_0-v_1\right|=0$ and, $\left|e_0-e_1\right|=1$. Thus $P_{4r+2}$ is directed cordial. Figure 6 illustrates the directed cordial path $P_6$.

Case (4). $P_m;m\equiv 3\left(\mathrm{mod}4\right)$.

Figure 3. Linearly directed cordial path P₂ and P₃.

Figure 4. Linearly directed cordial path P₈.

Figure 5. Linearly directed cordial path P₅.

Figure 6. Linearly directed cordial path P₆.

Suppose that $m=4r+3;r\ge 1$. Then, one can choose the labeling $M_{2r+1}$ for $P_{4r+3}$. Therefore, $x_0=2r+1,x_1=2r$, and $a_0=a_1=2r$. Consequently, $\left|v_0-v_1\right|=1$ and, $\left|e_0-e_1\right|=0$. Thus $P_{4r+3}$ is directed cordial. Figure 7 illustrates the directed cordial path $P_7$. Thus the lemma is proved.

4. The Directed Cordiality of $P_n^2$

It is known that the number of edges in $P_n^2$ is $2n-3$. In this section we show that $P_n^2$ is directed cordial for all positive integers $n\ge 2$.

Theorem 4.1. Each directed second power path, $P_n^2$, is directed cordial for all $n\ge 2$.

Proof: By previous theorem $P_2^2\cong P_2$.

Now, we need to study the following four cases:

Case (1). $P_n^2;n\equiv 0\left(\mathrm{mod}4\right)$.

Suppose that $n=4r;r\ge 1$. Without loss of generality, we may take the anti-clock direction throughout. Then, one can choose the labeling, $L_{4r}$ for $P_{4r}$.Therefore, $x_0=x_1=2r,a_0=4r-1$, and $a_1=4r-2$. Consequently, $\left|v_0-v_1\right|=0$ and, $\left|e_0-e_1\right|=1$. Figure 8 illustrates the directed cordial path $P_8^2$.

Case (2). $P_n^2;n\equiv 1\left(\mathrm{mod}4\right)$.

Suppose that $n=4r+1;r\ge 1$. Then, one can choose the labeling, $M_{2r+1}$ for $P_{4r+1}$. Therefore, $x_0=2r+1,x_1=2r,a_0=4r-1$, and $a_1=4r$. Consequently, $\left|v_0-v_1\right|=\left|e_0-e_1\right|=1$. Figure 9 illustrates the directed cordial path $P_9^2$.

Case (3). $P_n^2;n\equiv 2\left(\mathrm{mod}4\right)$.

Suppose that $n=4r+2;r\ge 1$. Then, one can choose the labeling, ${M^{\prime }}_{2r}10$ for $P_{4r+2}$. Therefore, $x_0=x_1=2r+1,a_0=4r+1$, and $a_1=4r$. Consequently, $\left|v_0-v_1\right|=0$ and, $\left|e_0-e_1\right|=1$. Figure 10 illustrates the directed cordial path $P_6^2$.

Case (4). $P_n^2;n\equiv 3\left(\mathrm{mod}4\right)$.

Suppose that $n=4r+3;r\ge 0$. Then, one can choose the labeling, $M_{2r}1$ for $P_{4r+3}$. Therefore, $x_0=2r+1,x_1=2r+2,a_0=4r+2$ and $a_1=4r+1$. Consequently, $\left|v_0-v_1\right|=\left|e_0-e_1\right|=1$.

Figure 7. Linearly directed cordial path P₇.

Figure 8. Linearly directed cordial path $P_8^2$.

Figure 9. Linearly directed cordial path $P_9^2$.

Figure 10. Linearly directed cordial path $P_6^2$.

Figure 11 illustrates the directed cordial path $P_{11}^2$. Thus the theorem is proved.

5. The Union of Two Directed Paths

In this section we study the directed cordiality of union of two directed paths $P_n$ and $P_m$. Throughout, we use the following inequalities to prove the directed cordiality.

$\left|v_0-v_1\right|=\left|\left(x_0-x_1\right)+\left(y_0-y_1\right)\right|\le 1$

$\left|e_0-e_1\right|=\left|\left(a_0-a_1\right)+\left(b_0-b_1\right)\right|\le 1$

Lemma 5.1. The union $P_n\cup P_m$ of two directed paths is always directed cordial for all $n,m\ge 2$.

Proof: There are three cases to be examined:

Figure 11. Linearly directed cordial path $P_{11}^2$.

Case (1). $P_{2r}\cup P_{2s}$

Choose the labeling ${M^{\prime }}_{2s}$ for $P_{2r}$ and $M_{2r}$ for $P_{2s}$. Then

$x_0=x_1=r$, $a_0=r$, $a_1=r-1$, $y_0=y_1=s$, $b_0=s-1$, and $b_1=s$.

Therefore

$\left|v_0-v_1\right|=\left|\left(x_0-x_1\right)+\left(y_0-y_1\right)\right|=\left|r-r+s-s\right|=0$

and

$\left|e_0-e_1\right|=\left|\left(a_0-a_1\right)+\left(b_0-b_1\right)\right|=\left|r-r+1+s-1-s\right|=0$.

Thus $P_{2r}\cup P_{2s}$ is directed cordial as we wanted to show.

Case (2). $P_{2r+1}\cup P_{2s+1}$

Choose the labeling $M_{2r+1}$ for $P_{2r}$ and ${M^{\prime }}_{2s+1}$ for $P_{2s}$. Then

$x_0=r+1$, $x_1=a_0=a_1=r$, $y_0=s$, $y_1=s+1$, and $b_0=b_1=s$.

Therefore

$\left|v_0-v_1\right|=\left|r+1-r+s-s-1\right|=0$

and

$\left|e_0-e_1\right|=\left|r-r+s-s\right|=0$.

Thus $P_{2r+1}\cup P_{2s+1}$ is directed cordial.

Case (3). $P_{2r}\cup P_{2s+1}$

Choose the labeling $M_{2r+1}$ for $P_{2r}$ and ${M^{\prime }}_{2s+1}$ for $P_{2s}$.Then

$x_0=x_1=r$, $a_0=r$, $a_1=r-1$, $y_0=s$, $y_1=s+1$, and $b_0=b_1=s$.

Therefore

$\left|v_0-v_1\right|=\left|r-r+s-s-1\right|=1$

and

$\left|e_0-e_1\right|=\left|r-r+1+s-s\right|=1$.

Thus, $P_{2r}\cup P_{2s+1}$ is directed cordial and the lemma is proved.

6. The Union of Two Directed Paths

In this section we give some sufficient conditions for the sum of two linearly directed paths $P_n$ and $P_m$ to be directed cordial. As indicted in the introduction we shall use the following equations to show that $P_n+P_m$ is directed cordial:

$\left|v_0-v_1\right|=\left|\left(x_0-x_1\right)+\left(y_0-y_1\right)\right|$,

and

$\left|e_0-e_1\right|=\left|\left(a_0-a_1\right)+\left(b_0-b_1\right)-m\left(x_0-x_1\right)\right|$.

Lemma 6.1. If n is even, and $P_n$ and $P_m$ have the same orientation. Then $P_n+P_m$ is directed cordial for all m.

Proof. Let us first study the following two special cases:

Let $n=m=2$ ; then the labeling [01; 10] is sufficient for $P_2+P_2$. Let $n=2$ and $m=3$ ; then we choose the labeling [10; 010] for $P_2+P_2$. Therefore, $x_0=x_1=1$, $a_0=1$, $a_1=0$, $y_0=2$, $y_1=1$, and $b_0=b_1=1$. Hence, $\left|v_0-v_1\right|=\left|e_0-e_1\right|=1$, so $P_2+P_3$ is directed cordial. See Figure 12.

To complete the proof, we need to examine the following two cases.

Case (1). m is even.

Let $n=2r,r>2$ and $m=2s,s>2$. Then one can choose the labeling $\left[M_{2r};{M^{\prime }}_{2s}\right]$ for $P_{2r}+P_{2s}$, where without loss of generality, we consider the given direction to both $b_n$ and $b_m$ is from left to right. It follows that, $x_0=x_1=r$, $a_0=r-1$, $a_1=r$, $y_0=y_1=s$, $b_0=s$, and $b_1=s-1$. Therefore,

$\left|v_1-v_0\right|=\left|\left(x_1-x_0\right)+\left(y_1-y_0\right)\right|=0$,

and $\left|e_1-e_0\right|=\left|\left(a_1-a_0\right)+\left(b_1-b_0\right)-m\left(x_1-x_0\right)\right|=0$. So, $P_{2r}+P_{2s}$ is directed cordial.

Case (2). m is odd.

Let $n=2r,r>2$ and $m=2s+1,s>1$. Then one can choose the labeling $\left[M_{2r};{M^{\prime }}_{2s+1}\right]$ for $P_{2r}+P_{2s+1}$. Then

$x_0=x_1=r$, $a_0=r$, $a_1=r-1$, $y_0=s$, $y_1=s+1$, and $b_0=b_1=s$,

Therefore

$\left|v_0-v_1\right|=\left|\left(x_0-x_1\right)+\left(y_0-y_1\right)\right|=\left|r-r+s-s-1\right|=1$,

and

$\begin{array}{c}\left|e_0-e_1\right|=\left|\left(a_0-a_1\right)+\left(b_0-b_1\right)-m\left(x_0-x_1\right)\right|\\ =\left|r-r+1+s-s-(2s+1)\left(r-r\right)\right|=1\end{array}$

Thus $P_{2r}+P_{2s+1}$ is directed cordial. Hence, the lemma is proved.

It is very important noting that, although $K_4$ is directed cordial, but according to Cahit, $K_4$ is not cordial [3]. This shows a difference between cordial graphs and directed cordial graphs.

Figure 12. Directed cordial path $P_2+P_3$.

Lemma 6.2. If n is odd, and $P_n$ and $P_2$ have the same direction. Then $P_n+P_2$ is directed cordial.

Proof: Let $n=2r+1,r\ge 1$. Then one can choose the labeling $\left[M_{2r+1};10\right]$ for $P_{2r+1}+P_2$. It follows that $x_0=r+1$, $x_1=r$, $a_0=a_1=r$, $y_0=y_1=1$, $b_0=1$, and $b_1=0$. Hence $\left|v_0-v_1\right|=\left|e_0-e_1\right|=1$. See Figure 13 and Figure 14.

Lemma 6.3. If n is odd, and both $P_n$ and $P_3$ are similarly directed. Then $P_n+P_3$ is directed cordial.

Proof. Suppose that $n=2r+1$. Then one can choose the labeling $\left[0_r{1}_{r+1};0_{2}1\right]$ for $P_n+P_3$. It follows that $x_0=r$, $x_1=r+1$, $a_0=a_1=r$, $y_0=2$, $y_1=1$, $b_0=0$, and $b_1=2$. It is easy to show that $\left|v_0-v_1\right|=0$ and $\left|e_0-e_1\right|=1$. Thus, $P_{2r+1}+P_3$ is directed cordial. See Figure 15.

Lemma 6.4. If n is odd and both $P_n$ and $P_4$ are similarly directed. Then $P_n+P_4$ is directed cordial.

. Suppose that $n=2r+1$, and $P_n$ and $P_4$ have the same direction. Then one can choose the labeling $\left[0_r{1}_{r+1};0_{3}1\right]$ for $P_{2r+1}+P_4$. It follows that $x_0=r$, $x_1=r+1$, $a_0=a_1=r$, $y_0=3$, $y_1=1$, $b_0=0$, and $b_1=3$. Hence $\left|v_0-v_1\right|=\left|e_0-e_1\right|=0$, and so, $P_{2r+1}+P_4$ is directed cordial. See Figure 16.

Figure 13. Directed cordial path $P_3+P_2$.

Figure 14. Directed cordial path $P_5+P_2$.

Figure 15. Directed cordial path $P_5+P_3$.

Figure 16. Directed cordial path $P_3+P_4$.

7. Applications and Conclusions

The water and gas pipelines supply to a building represent examples of diagraphs. We think of edges of a directed path as pipes can flow through it in one way flow. Another example is the waste systems of plumbing in a building. In conclusion, the directed paths, second power directed paths and the union of any two directed paths are all cordial digraphs. If n is even, then the join $P_n+P_m$ is always cordial diagraph. Also, $P_n+P_i$ is cordial digraph for all $i=2,3,4$, and n is odd.

Conflicts of Interest

The authors declare no conflicts of interest regarding the publication of this paper.

References

[1]	Gallian, J.A. (2017) A Dynamic Survey of Graph Labeling. The Electronic Journal of Combinatorics, Twentieth Edition, December 22, 1-432. https://www.combinatorics.org/ojs/index.php/eljc/article/view/DS6/versions
[2]	Harary, F. (1972) Graph Theory. Addison-Wesley Reading Mass, Massachusetts.
[3]	Diab, A.T. (2010) On Cordial Labeling of the Second Power of Paths with Other Graphs. ARS-Combinatoria, 97A, 327-343.
[4]	Cahit, I. (1987) Cordial Graphs: A Weaker Version of Graceful and Harmonious Graphs. ARS-Combinatoria, 23, 201-207.
[5]	Cahit, I. (1990) On Cordial and 3-Eqtitable Labeling of Graphs. Utilitas Mathematica, 37, 189-198.