(2,3)-Cordial Oriented Hypercubes

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.

We proceed by induction on the dimension $n$ in multiples of $3$. Example 3.3 serves as a base case for $n=3$. Suppose the claim is true for some $k$ that is a multiple of $3$. Then there exists some oriented hypercube $Q_{k}=(V_{k},A_{k})$ of dimension $k$ that is $(2,3)$-cordial. That is, there exists a friendly labeling $f\colon V_{k}\to\{0,1\}$ such that

$$\Lambda_{f,g}=\left(\frac{1}{3}|A_{k}|,\frac{1}{3}|A_{k}|,\frac{1}{3}|A_{k}|\right)$$

where $g$ is defined as in Definition 2.2. We aim to construct an oriented hypercube $Q_{k+3}=(V_{k+3},A_{k+3})$ of dimension $k+3$ that is $(2,3)$-cordial. We begin by constructing an oriented hypercube $Q_{k+1}=(V_{k+1},A_{k+1})$ of dimension $k+1$. Let $L_{k}$ denote the digraph $Q_{k}$ with vertex labeling $f$ and induced arc labeling $g$ applied and $\overline{L_{k}}$ denote the digraph $Q_{k}$ with vertex labeling $\overline{f}$ and induced arc labeling $\overline{g}$. Now, let us draw arcs from $L_{k}$ to $\overline{L_{k}}$ according to the trivial digraph isomorphism. That is, define an arc initiating at vertex $x$ in $L_{k}$ to vertex $y$ in $\overline{L_{k}}$ if and only if $x=y$. We then label each of these arcs as $\overline{f}(x)-f(x).$ The result is a labeled digraph, call it $L_{k+1}$. By construction, the underlying digraph of $L_{k+1}$ is an oriented hypercube of dimension $k+1$, call it $Q_{k+1}$. Define $f_{k+1}$ and $g_{k+1}$ to be vertex and arc labelings of $Q_{k+1}$ respectively such that $Q_{k+1}$ with labelings $f_{k+1}$ and $g_{k+1}$ applied is the labeled oriented hypercube $L_{k+1}$. As $f_{k+1}$ applies friendly labelings $f$ and $\overline{f}$ to complementary subgraphs of $Q_{k+1}$, $f_{k+1}$ is a friendly labeling. Further, $g_{k+1}$ applies $g$ and $\overline{g}$ to complementary subgraphs of $Q_{k+1}$ and labels each arc $\overrightarrow{xx}$ from $L_{k}$ to $\overline{L_{k}}$, $\overline{f}(x)-f(x)$. Then, as $f$ and $\overline{f}$ are friendly,

$$\Lambda_{f_{k+1},g_{k+1}}=\left(\frac{2}{3}|A_{k}|+2^{k-1},\frac{2}{3}|A_{k}|+2^{k-1},\frac{2}{3}|A_{k}|\right).$$

Now, we repeat our procedure, constructing an oriented hypercube $Q_{k+2}=(V_{k+2},A_{k+2})$ of dimension $k+2$. We draw arcs from $L_{k+1}$ and $\overline{L_{k+1}}$. Just as in the previous case, we define an arc from a vertex $x$ in $L_{k+1}$ to vertex $y$ in $\overline{L_{k+1}}$ if and only if $x=y$, and we label this arc $\overline{f_{k+1}}(x)-f_{k+1}(x)$. The result, as in the previous step, is a labeled digraph, call it $L_{k+2}$. The underlying digraph of $L_{k+2}$ is again an oriented hypercube, now of dimension $k+2$, call it $Q_{k+2}$. As before, define $f_{k+2}$ and $g_{k+2}$ to be vertex and arc labelings of $Q_{k+2}$ respectively such that when applied to $Q_{k+2}$ yield the labeled oriented hypercube $L_{k+2}$. As before, $f_{k+2}$ applies friendly labelings $f_{k+1}$ and $\overline{f_{k+1}}$ to complementary subgraphs, thus $f_{k+2}$ is friendly. Also, $g_{k+2}$ applies $g_{k+1}$ and $\overline{g_{k+1}}$ to complementary subgraphs of $Q_{k+2}$ and labels each arc $\overrightarrow{xx}$ from $L_{k+1}$ to $\overline{L_{k+1}}$, $\overline{f_{k+1}}(x)-f_{k+1}(x)$ and $\bar{f}$. As $f_{k+1}$ and $\overline{f_{k+1}}$ are friendly,

$$\Lambda_{f_{k+2},g_{k+2}}\left(\left(\frac{4}{3}|A_{k}|+2^{k}\right)+2^{k},\left(\frac{4}{3}|A_{k}|+2^{k}\right)+2^{k},\frac{4}{3}|A_{k}|\right).$$

In our final step, we construct an oriented hypercube $Q_{k+3}=(V_{k+3},A_{k+3})$ of dimension $k+3$ by drawing edges between two identically labeled cubes $L_{k+2}$. We draw an arc from vertex $x$ in the first $L_{k+2}$ to vertex $y$ in the second $L_{k+2}$ if and only if $x=y$ and we label this arc $f_{k+2}(x)-f_{k+2}(x)=0$. The result is a labeled digraph, call it $L_{k+3}$. The underlying digraph of $L_{k+3}$ is an oriented hypercube of dimension $k+3$, call it $Q_{k+3}$. Finally, we define $f_{k+3}$ and $g_{k+3}$ to be vertex and arc labelings of $Q_{k+3}$ respectively such that when applied to $Q_{k+3}$ yield the labeled oriented hypercube $L_{k+3}$. Then $f_{k+3}$ simply labels each complementary subgraph $Q_{k+2}$ according to $f_{k+2}$ and $g_{k+3}$ labels each complementary subgraph $Q_{k+2}$ according to $g_{k+2}$ and the newly drawn $2^{k+2}$ edges are labeled $0$. Let $\omega=\frac{4}{3}|A_{k}|+2^{k+1}$. Then

$$\Lambda_{f_{k+3},g_{k+3}}(Q_{k+3})=\left(2\omega,2\omega,\frac{8}{3}|A_{k}|+2^{k+2}\right).$$

Simplifying, we have

$$\Lambda_{f_{k+3},g_{k+3}}(Q_{k+3})=\left(\frac{1}{3}(k+3)2^{k+2},\frac{1}{3}(k+3)2^{k+2},\frac{1}{3}(k+3)2^{k+2}\right).$$

As $f_{k+3}$ is constructed to be a friendly labeling, the above implies $Q_{k+3}$ is $(2,3)$-cordial.

There are $\binom{8}{4}$ possible friendly vertex labelings for the oriented cube $V$. By a brute force algorithm, it can be shown that none of these vertex labelings induces a $(2,3)$-cordial labeling.

By Lemma 2.5.1, $\Lambda_{f,g}(V)=\Lambda_{f,g}(V^{R})$ for any vertex-arc labeling $f,g$. Thus, given $V$ does not admit a $(2,3)$-cordial labeling by Theorem 4.1, neither does $V^{R}$. Equivalently, $V^{R}$ is not $(2,3)$-cordial.

This can be shown by a simple brute force algorithm.