Cordial Digraphs

1. Introduction

Let ${\mathcal{G}}_n$ denote the set of all simple undirected graphs on the vertex set $V=\{v_1,v_2,\dots ,v_n\}$. For $G\in {\mathcal{G}}_n$, let $E(G)$ denote the edge set of $G$. In the article “Cordial graphs: A Weaker Version of Graceful and Harmonious Graphs”, Ibrahim Cahit introduced cordial graphs. Relative definitions are found in the next section. In this article we are interested in directed graphs and so, the orientation of an arc is essential in any investigation. While the induced labelings in undirected graphs are symmetric, we shall want the arc labelings of our directed graphs to be asymmetric. The study of cordial graphs has been to identify classes of graphs that have a friendly labeling that induces a cordial labeling of the edges. We shall proceed in that fashion for directed graphs.

2. Preliminaries

In this article, we will be concerned mainly with digraphs, We let ${\mathcal{D}}_n$ denote the set of all simple directed graphs on the vertex set $V=\{v_1,v_2,\dots ,v_n\}$. Further, we shall want no arcs directed both ways between any pair of vertices, that is our graphs will be digon-free. Thus we shall let ${\mathcal{T}}_n$ denote the set of all subgraphs of a tournament digraph. Let $D\in {\mathcal{T}}_n$, $D=(V,A)$ where $A$ is the arc set of $D$. Then $D$ has no loops, no digons, and no multiple arcs. An arc in $D$ directed from vertex $u$ to vertex $v$ will be denoted $\overrightarrow{uv},\overleftarrow{vu}$ or by the ordered pair $(u,v)$. We also let ${\mathcal{G}}_n$ denote the set of all simple undirected graphs on the vertex set $V=\{v_1,v_2,\dots ,v_n\}$. So all members of ${\mathcal{T}}_n$ are orientations of graphs in ${\mathcal{G}}_n$.

A $(0,1)$-labeling of a finite set, $\mathcal{Z}$, is a mapping $f:\mathcal{Z}\to \{0,1\}$ and is said to be friendly if approximately one half of the members of $\mathcal{Z}$ are labeled 0 and the others are labeled 1, that is $-1\le |f^{-1}(0)|-|f^{-1}(1)|\le 1$ where $|\mathcal{X}|$ denotes the cardinality of the set $\mathcal{X}$. If there are an even number of elements in $\mathcal{Z}$ , then a friendly labeling has the number labeled 1 equal to the number labeled 0. More generally we define an $\mathcal{A}$-friendly labeling:

Note that a labeling is A-friendly means that the labels are as nearly evenly distributed as possible. If the cardinality of Z  is a multiple of the cardinality of A  then $|f^{-1}(i)|=|f^{-1}(j)|$ for any $i,j\in \mathcal{A}$. If the set A  is obvious from the context we just say that $f$ is friendly.

Let $G=(V,E)$ be an undirected graph with vertex set $V$ and edge set $E$, and let $f$ be a friendly (0,1)-labeling of the vertex set $V$. Given this friendly vertex labeling $f$, an induced $(0,1)$-labeling of the edge set is a mapping $g:E\to \{0,1\}$ where for an edge $uv,g(uv)=\hat{g}(f(u),f(v))$ for some $\hat{g}:\{0,1\}\times \{0,1\}\to \{0,1\}$ and is said to be cordial if $g$ is also friendly, that is $-1\le |g^{-1}(0)|-|g^{-1}(1)|\le 1$. A graph, $G$, is called cordial if there exists a induced cordial labeling of the edge set of $G$. The induced labeling $g$ is usually $g(u,v)=\hat{g}(f(u),f(v))=|f(v)-f(u)|$ [1], $g(u,v)=\hat{g}(f(u),f(v))=f(v)+f(u)$ (in ${\mathbb{Z}}_2$) [2], or $g(u,v)=\hat{g}(f(u),f(v))=f(v)f(u)$ (product cordiality) [3].

In[2], Hovey introduced $\mathcal{A}$-friendly labelings. A labeling $f:V(G)\to \mathcal{A}$ is said to be $\mathcal{A}$-friendly if given any $a,b\in \mathcal{A}$, $-1\le |f^{-1}(b)|-|f^{-1}(a)|\le 1$. If $g$ is an induced edge labeling and $f$ and $g$ are both $\mathcal{A}$-friendly Then $g$ is said to be an $\mathcal{A}$-cordial labeling and $G$ is said to be $\mathcal{A}$-cordial. When $\mathcal{A}={\mathbb{Z}}_k$ we say that $G$ is $k$-cordial. We shall use this concept with digraphs.

Let $D=(V,A)$ be a directed graph with vertex set $V$ and arc set $A$. Let $f:V\to \{0,1\}$ be a friendly labeling of the vertices of $D$. As for undirected graphs, an induced labeling of the arc set is a mapping $g:A\to \mathcal{X}$ for some set $\mathcal{X}$ where for an arc $(u,v)=\overrightarrow{uv},g(u,v)=\hat{g}(f(u),f(v))$ for some $\hat{g}:\{0,1\}\times \{0,1\}\to \mathcal{X}$. As we are dealing with directed graphs, it would be desirable for the induced labeling to distinguish between the label of the arc $(u,v)$ and the label of the arc $(v,u)$, otherwise, the labeling would be an induced labeling of the underlying undirected graph. If we let $\mathcal{X}={\mathbb{Z}}_3=\{-1,0,1\}$ and $\hat{g}(f(u),f(v))=f(v)-f(u)$, we have an asymmetric labeling. In this case, if the set of arcs are nearly equally distributed among the three labelings, we say that the labeling is $(2,3)$-cordial. Formally:

For any digraph $D$ with $(0,1)$-vertex labeling $f$, and induced $(0,1,-1)$-arc labeling $g$, let ${\mathrm{\Lambda }}_{f,g}(D)=(\alpha ,\beta ,\gamma )$ where $\alpha =|g^{-1}(1)|,\beta =|g^{-1}(-1)|,$ and $\gamma =|g^{-1}(0)|$.

Let $D\in {\mathcal{T}}_n$ and let $D^R$ be the digraph such that every arc of $D$ is reversed, so that $\overrightarrow{uv}$ is an arc in $D^R$ if and only if $\overrightarrow{vu}$ is an arc in $D$. Let $f$ be a $(0,1)$-labeling of the vertices of $D$ and let $g(\overrightarrow{uv})=f(v)-f(u)$ so that $g$ is a $(1,-1,0)$-labeling of the arcs of $D$. Let $\overline{f}$ be the complementary $(0,1)$-labeling of the vertices of $D$, so that $\overline{f}(v)=0$ if and only if $f(v)=1$. Let $\overline{g}$ be the corresponding induced arc labeling of $D$, $\overline{g}(\overrightarrow{uv})=\overline{f}(v)-\overline{f}(u)$.

Proof. If an arc is labeled 1, -1, 0 respectively then reversing the labeling of the incident vertices gives a labeling of -1, 1, 0 respectively, If an arc $\overrightarrow{uv}$ is labeled 1, -1, 0 respectively, then $\overrightarrow{vu}$ would be labeled -1, 1, 0 respectively.

3. (2,3)-Cordial Digraphs

In this section, we shall use the arc labeling function $g:A\to \{0,1,-1\}$ defined by $g(\overrightarrow{v_i{v}_j})=g(v_i,v_j)=f(v_j)-f(v_i)$ where $f$ is a $(0,1)$-labeling of the vertices.

3.1. (2,3)-cordial labelings of orientations of small trees

We now give labelings of orientations of small trees to be used in inductive proofs later.

Let $P_n$ be a path of order $n$ (the number of vertices, so that there are $n-1$ arcs in $P_n$). For $n=1$, there is only one directed graph and it is vacuously (2,3)-cordial. For $n=2$ the only tree is an edge graph and any orientation is the digraph of an arc, which is (2,3)-cordial if the labelings of the two vertices are different.

For $n=3$, every tree is a 2-path and so there are only two (non-isomorphic) orientations. We list them here with (2,3)-cordial labelings:

For $n=4$ there are two undirected trees with three different (non-isomorphic) orientations of the 4-path and two non-isomorphic orientations of the star on 4 vertices. Here we give these five oriented trees with (2,3)-cordial labelings of three of them: See Figures 2 and 3.

3.1.1. (2,3)-Cordial Stars

Recall that for a friendly labeling $f$ of the vertices we let $g$ be the induced labeling of the arcs defined by $g(u,v)=f(v)-f(u)$.

Let $S\in {\mathcal{G}}_n$ be a star graph with central vertex $v$ and $n-1$ pendant vertices. A natural question is: Is there an orientation of $S$ that is (2,3)-cordial? Another is: Are all orientations of $S$ (2,3)-cordial? The answer to the latter question is: Only if $n\le 3$. The answer to the first question is more complicated, but is completely answered here.

Let $n\ge 4$. There are six cases to consider: $n$ is even or odd and $n$ is a multiple of three, one more than a multiple of three or two more than a multiple of three. Investigating these six cases, we let $k$ and $\ell$ be positive integers.

Case 1. $n$ is even, $n=2k$. Here there must be $k-1$ pendant vertices labeled the same as the labeling of the central vertex $v$. Since $n\ge 4$, $k\ge 2$, we have that $\lceil \frac{k}{2}\rceil \le k-1$. For $g$ to be friendly, we must have $k-1$ arcs labeled 0, $\lceil \frac{k}{2}\rceil$ arcs labeled either 1 or -1 respectively, and $\lfloor \frac{k}{2}\rfloor$ arcs labeled -1 or 1 respectively.

Subcase a. The number of arcs is $n-1=3\ell$ so that $n=3\ell +1$. For $S$ to be (2,3)-cordial we must have $k-1=\ell$. But then $2k=n=3\ell +1=3(k-1)+1$ so that $k=2$ and $n=4$.

Subcase b. The number of arcs is $n-1=3\ell +1$, so that $n=3\ell +2$. For $S$ to be (2,3)-cordial we must have $k-1=\ell +1$ or $k=\ell +2$. Hence $n=2k=2\ell +4=3\ell +2$, so that, $\ell =2$ , $k=4$ and $n=8$.

Subcase c. The number of arcs is $n-1=3\ell +2$ so that $n=3\ell +3$. For $S$ to be (2,3)-cordial we must have $k-1=\ell +1$ or $k=\ell +2$. Thus, $n=2k=2\ell +4=3\ell +3$ so that $\ell =1$ and $n=6$.

Thus, since any orientation of a 2-star is $(2,3)$-cordial, when $n$ is even we have that $n=2,4,6$ or $8$ only.

Case 2. $n$ is odd, $n=2k+1$. Since for $n=1$ or 3, every orientation of a 1-star or 3-star is $(2,3)$-cordial, we assume that $n\ge 5$ and thus $\lceil \frac{k}{2}\rceil \le k-1$. Hence there are $k-1$ pendant vertices labeled the same as the labeling of the central vertex $v$. So there are $k-1$ arcs labeled 0.

Subcase a. The number of arcs is $n-1=3\ell$ so that $n=3\ell +1$. For $S$ to be (2,3)-cordial we must have $k-1=\ell$ so that $k=\ell +1$ and hence $3\ell +1=n=2k+1=2\ell +3$ and hence $\ell =2$ and $n=7$.

Subcase b. The number of arcs is $n-1=3\ell +1$ so that $n=3\ell +2$. For $S$ to be (2,3)-cordial we must have $k-1=\ell$ or $k=\ell +1$ and $\frac{k}{2}=\ell$ so that $n=5$; or $k-1=\ell +1$ and $k=\ell +2$, so that $n=11$.

Subcase c. The number of arcs is $n-1=3\ell +2$ so that $n=3\ell +3$. For $S$ to be (2,3)-cordial we must have $k-1=\ell +1$ so $k=\ell +2$. Thus, $3\ell +3=n=2k+1=2\ell +5$. Hence $l=2$ and $n=9$.

Thus, when $n$ is odd, we have that $n=1,3,5,7,9$ or 11 only.

The above analysis establishes:

3.1.2. (2,3)-Cordiality of Directed Cycles and Paths

Proof. The labeling of an $n$-cycle is shown in Figure 4, where $k=2\ell$ and $n=3k=6\ell$. The vertex labeling is outside the cycle and the induced edge labeling is inside the cycle. By deleting $1,2,\dots ,5$ vertices, carefully chosen, one obtains a $(2,3)$-cordial labeling of a cycle of any length. By deleting one edge, carefully chosen, one obtains a $(2,3)$-cordial labeling of any directed path. Thus, conclusions 1 and 2 are proven.

If $D$ is an out-star with central vertex $v$, then, if the vertex $v$ is labeled “0”, all arcs are labeled either “0” or “-1”, while if the vertex $v$ is labeled “1”, all arcs are labeled either “0” or “1” Thus, no labeling is (2,3)-cordial. A parallel argument holds for an in-star.

It is easily shown, even though time consuming, that both of the non-isomorphic tournaments on 3 vertices are (2,3)-cordial while only three of the four non-isomorphic tournaments on four vertices are cordial; the 4-tournament with score vector (1,1,1,3) is not (2,3)-cordial.

Paths

Proof. For $n=1$ or $n=2$ the lemma is trivially established. For $n=3$ the two orientations in Figure 1 (and consequently their reversals) are shown to be (2,3)-cordial.

For $n=4$, the four orientations of the 4-path that are not in Figure 5 are shown to be (2,3)-cordial in Figure 6.

For $n=5,6,$ and $7$, see the appendices, There is a (2,3)-cordial labeling of each orientation of the paths of length 5, 6, and 7.

For $n=8$, append a vertex to the end of each orientation of the path on 7 vertices and obtain two orientations of the 8-path, one with $\overrightarrow{v_7{v}_8}$ and the other with $\overleftarrow{v_7{v}_8}$. By labeling vertex $v_8$ with 0 if there are fewer vertices in the labeling of the orientation of $P_7$ labeled 0 than 1 and labeling vertex $v_8$ a 1 otherwise we get a $(2,3)$-cordial labeling. Thus, we get a (2,3)cordial labeling of all 128 orientations of $P_8$.

For $n=9$, append a vertex to the end of each orientation of the path on 8 vertices and obtain two orientations of the 9-path, one with $\overrightarrow{v_8{v}_9}$ and the other with $\overleftarrow{v_8{v}_9}$. By choosing appropriately the label of $v_9$ one gets a (2,3)-cordial labeling. This gives a (2,3)-cordial labeling of all 256 orientations of $P_9$.

Note that in the sequel, only vertex labelings are given as the arc labels are implicit. For example in Figures 5 and 6 we give the 4-paths that are (2,3)-cordial and the 4-paths that are not (2,3)-cordial.

The author wishes to thank the referee for his valuable suggestions.