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
is an alternating sequence of distinct vertices and
edges.
is said to be linearly directed if all its edges have the same direction: clockwise or counterclockwise. The distance
between two vertices
in V of a graph
is the length of shortest path joining them in G. The second power of a path
, denoted
, is the union of
and the set of all edges
with distance 2 and
. In Particular
,
[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
is cordial if and only if
and a complete bipartite graph
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
be a digraph and let
be a labeling of its vertices and its set of edges, and let
be linearly directed (see Figure 1).
We define the edge labeling as follows
Let
and
be the numbers of vertices that are labeled by 0 and 1, respectively, in G and let
and
be the corresponding numbers of edges. Such a labeling is called cordial if both
and
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
that are endowed with directions defined as follows:
and
have the same orientation (see Figure 2).
Given two disjoint paths
and
, then their union,
, is simply the unions of their sets of vertices and edges. If
and
represent the numbers of vertices and edges that are labeled i in
, respectively, and the corresponding quantities for
are
and
. Therefore, it is obvious that
and
.
The join (sum)
is obtained from
by adding all edges that join each vertex of
to all vertices of
. Consider
and
have the same orientation. Then, we define the direction of all new edges that are connecting vertices of
and
to be from vertices of
to vertices of
. It follows that
, and
.
We shall show that
and
are directed cordial for all positive integers n, m. Some sufficient conditions are given to make the join
is directed cordial. It is worth noting that, although
is directed cordial but according to Cahit [5], it is not cordial.
Figure 2. The Directed Second Power of a Path Have The Same Orientation.
2. Terminology and Notation
Let
denote the labeling
(r times), and the labeling
is denoted by
. We let
denote the labeling
. Let
denote the labeling
(r-times) and
denote the labeling
(r-times), where
. The labeling
(r-times) is denoted by
. Similarly,
(r-times) is denoted by
. We can modify this by adding symbols at one end or the other (or both), thus
denotes the labeling
, when
and 101 when
. Similarly,
is the labeling
when
and 01 when
.
3. Directed Cordial Paths
Let
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
, is directed cordial;
.
Proof: Let us first examine the particular cases
and
.
For
, we choose the labeling 01; therefore
. Without any loss of generality, one may use the clockwise direction and hence
, and,
. So
is directed cordial.
For
, we choose the labeling 010; therefore
, and
, also we may consider the direction of
as done in
; hence
and
, so
is directed cordial (Figure 3).
To complete the proof, we need to study the following four cases:
Case (1).
.
Suppose that
. We choose the labeling,
for
. Therefore
,
, and
. Consequently,
and,
. Thus
is directed cordial. Figure 4 illustrates the directed cordial path
.
Case (2).
.
Suppose that
. Then, one can choose the labeling,
for
. Therefore
, and
. Consequently,
and,
. Thus
is directed cordial. Figure 5 illustrates the directed cordial path
.
Case (3).
.
Suppose that
. Then, one can choose the labeling,
for
. Therefore,
,
, and
. Consequently,
and,
. Thus
is directed cordial. Figure 6 illustrates the directed cordial path
.
Case (4).
.
Figure 3. Linearly directed cordial path P2 and P3.
Figure 4. Linearly directed cordial path P8.
Figure 5. Linearly directed cordial path P5.
Figure 6. Linearly directed cordial path P6.
Suppose that
. Then, one can choose the labeling
for
. Therefore,
, and
. Consequently,
and,
. Thus
is directed cordial. Figure 7 illustrates the directed cordial path
. Thus the lemma is proved.
4. The Directed Cordiality of
It is known that the number of edges in
is
. In this section we show that
is directed cordial for all positive integers
.
Theorem 4.1. Each directed second power path,
, is directed cordial for all
.
Proof: By previous theorem
.
Now, we need to study the following four cases:
Case (1).
.
Suppose that
. Without loss of generality, we may take the anti-clock direction throughout. Then, one can choose the labeling,
for
.Therefore,
, and
. Consequently,
and,
. Figure 8 illustrates the directed cordial path
.
Case (2).
.
Suppose that
. Then, one can choose the labeling,
for
. Therefore,
, and
. Consequently,
. Figure 9 illustrates the directed cordial path
.
Case (3).
.
Suppose that
. Then, one can choose the labeling,
for
. Therefore,
, and
. Consequently,
and,
. Figure 10 illustrates the directed cordial path
.
Case (4).
.
Suppose that
. Then, one can choose the labeling,
for
. Therefore,
and
. Consequently,
.
Figure 7. Linearly directed cordial path P7.
Figure 8. Linearly directed cordial path
.
Figure 9. Linearly directed cordial path
.
Figure 10. Linearly directed cordial path
.
Figure 11 illustrates the directed cordial path
. 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
and
. Throughout, we use the following inequalities to prove the directed cordiality.
Lemma 5.1. The union
of two directed paths is always directed cordial for all
.
Proof: There are three cases to be examined:
Figure 11. Linearly directed cordial path
.
Case (1).
Choose the labeling
for
and
for
. Then
,
,
,
,
, and
.
Therefore
and
.
Thus
is directed cordial as we wanted to show.
Case (2).
Choose the labeling
for
and
for
. Then
,
,
,
, and
.
Therefore
and
.
Thus
is directed cordial.
Case (3).
Choose the labeling
for
and
for
.Then
,
,
,
,
, and
.
Therefore
and
.
Thus,
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
and
to be directed cordial. As indicted in the introduction we shall use the following equations to show that
is directed cordial:
,
and
.
Lemma 6.1. If n is even, and
and
have the same orientation. Then
is directed cordial for all m.
Proof. Let us first study the following two special cases:
Let
; then the labeling [01; 10] is sufficient for
. Let
and
; then we choose the labeling [10; 010] for
. Therefore,
,
,
,
,
, and
. Hence,
, so
is directed cordial. See Figure 12.
To complete the proof, we need to examine the following two cases.
Case (1). m is even.
Let
and
. Then one can choose the labeling
for
, where without loss of generality, we consider the given direction to both
and
is from left to right. It follows that,
,
,
,
,
, and
. Therefore,
,
and
. So,
is directed cordial.
Case (2). m is odd.
Let
and
. Then one can choose the labeling
for
. Then
,
,
,
,
, and
,
Therefore
,
and
Thus
is directed cordial. Hence, the lemma is proved.
It is very important noting that, although
is directed cordial, but according to Cahit,
is not cordial [3]. This shows a difference between cordial graphs and directed cordial graphs.
Lemma 6.2. If n is odd, and
and
have the same direction. Then
is directed cordial.
Proof: Let
. Then one can choose the labeling
for
. It follows that
,
,
,
,
, and
. Hence
. See Figure 13 and Figure 14.
Lemma 6.3. If n is odd, and both
and
are similarly directed. Then
is directed cordial.
Proof. Suppose that
. Then one can choose the labeling
for
. It follows that
,
,
,
,
,
, and
. It is easy to show that
and
. Thus,
is directed cordial. See Figure 15.
Lemma 6.4. If n is odd and both
and
are similarly directed. Then
is directed cordial.
. Suppose that
, and
and
have the same direction. Then one can choose the labeling
for
. It follows that
,
,
,
,
,
, and
. Hence
, and so,
is directed cordial. See Figure 16.
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
is always cordial diagraph. Also,
is cordial digraph for all
, and n is odd.