#  (2,3)-Cordial Trees and Paths††thanks: AMS Classification number: 05C20,
05C38, 05C78  ††thanks: Key words and phrases: orientation of an undirected
graph, graph labeling, cordial labeling, (2,3)-cordial digraph

Manuel Santana
Department of Mathematics and Statistics
Utah State University
Logan, Utah 84322-3900, U.S.A
<EMAIL_ADDRESS>

Jonathan Mousley
Department of Mathematics and Statistics
Utah State University
Logan, Utah 84322-3900, U.S.A
<EMAIL_ADDRESS>

Dave Brown
Department of Mathematics and Statistics
Utah State University
Logan, Utah 84322-3900, U.S.A
<EMAIL_ADDRESS>

LeRoy B. Beasley
Department of Mathematics and Statistics
Utah State University
Logan, Utah 84322-3900, U.S.A
<EMAIL_ADDRESS>corresponding Author

###### Abstract

Recently L. B. Beasley introduced $(2,3)$-cordial labelings of directed graphs
in [1]. He conjectured that every orientation of a path of length at least
five is $(2,3)$-cordial, and that every tree of max degree $n=3$ has a cordial
orientation. In this paper we formally define $(2,3)-$cordiality from the
viewpoint of quasigroup cordiality. We show both conjectures to be false,
discuss the $(2,3)$-cordiality of orientations of the Petersen graph, and
establish an upper bound for the number of edges a graph can have and still be
$(2,3)$-orientable.

##  1 Introduction

Let $G=(V,E)$ be an undirected graph with vertex set $V$ and edge set $E$, a
convention we will use throughout this paper. A $(0,1)$-labelling of the
vertex set is a mapping $f:V\to\\{0,1\\}$ and is said to be friendly if
approximately one half of the vertices are labelled 0 and the others labelled
1. An induced labelling 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
$f$ is friendly and about one half the edges of $G$ are labelled 0. A graph,
$G$, is called cordial if there exists a cordial induced labelling of the edge
set of $G$.

In this article we investigate a cordial labelling of directed graphs that is
not merely a cordial labelling of the underlying undirected graph. This
labeling was introduced by L. B. Beasley in [1]. Let $D=(V,A)$ be a directed
graph with vertex set $V$ and arc set $A$, with a $(0,1)$ vertex set mapping
$f:V\to\\{0,1\\}$. Let $g:A\to\\{-1,0,1\\}$ be the induced labeling of the
arcs of $D$ such that for any $\overrightarrow{uv}$, by which we mean an arc
going from $u$ to $v$, $g(\overrightarrow{uv})=f(v)-f(u)$. The digraph $D$ is
said to be $(2,3)$-cordial if there exists a friendly labeling on $D$ with
this induced labeling on the arc set such that approximately one third of the
arcs receive each labeling. Applications of balanced graph labelings can be
found in the introduction of [7].

In this paper we will formally define $(2,3)$-cordiality starting from the
view of quasi-groups, resolve two conjecture posed in [1], both in the
negative, and discuss the $(2,3)$ cordiality of the Petersen graph and
complete graphs.

##  2 Preliminaries

In [4] Hovey introduced $A$ cordial graphs, with vertex labeling of an abelian
group $A$. We use the short hand that for any $a\in A$ that $V_{a},E_{a}$ is
the number of vertices or edges labeled $a$ respectively We repeat the
definition here, and then proceed to generalize it to the directed graph case.

######  Definition 2.1.

A labeling function $f$ is said to be balanced if it is surjective, and if for
all $a$ and $b$ in the image of $f$, $||f^{-1}(a)|-|f^{-1}(b)||\leq 1$.

######  Definition 2.2.

Let $A$ be an abelian group. A graph $G$ is is $A-$cordial if there is a
balanced labeling $f:V\to A$ that induces an edge labeling $f(a,b)=f(a)+f(b)$
such that the vertex labeling and edge labeling are balanced.

In [8] Penchenik and Wise generalized this idea by introducing quasi-group
cordiality. A quasi-group $Q$ is a set with binary operation $\cdot$ such that
for all $a,b\in Q$ there exist unique $c,d\in Q$ such that $a\cdot c=b$ and
$d\cdot a=b$. Particularly all (non-abelian) groups are quasi groups. They
offer the following definition for quasigroup cordiality.

######  Definition 2.3.

Let $Q$ be a quasi-group and $G$ a directed graph. A labeling $f:V\to Q$
induces a labeling of the arcs in the following way. If $(a,b)$ is an arc with
head $a$, then $f(a,b)=f(a)\cdot f(b)$. If there is a balanced vertex labeling
of $G$ that induces a balanced edge labeling of $G$, then we say that $G$ is
$Q-cordial$.

We extend this now to a different form of quasi-group Cordiality defined as
thus.

######  Definition 2.4.

Let $Q$ be a quasi-group with subset $\mathbb{Q}$ and $G$ a directed graph. A
labeling $f:V\to\mathbb{Q}$ induces an arc labeling as in definition 2.3. If
there is a balanced vertex labeling of $G$ that induces a balanced arc
labeling of $G$, then we say $G$ is $(\mathbb{Q},Q)-cordial$.

In this paper consider only the simplest case
$(\mathbb{Z}_{2},\mathbb{Z}_{3}^{-})-cordial$ defined by Beasly as
$(2,3)-$cordial in [1]. We will offer the formal definition of $(2,3)-$cordial
here.

######  Definition 2.5.

A labeling $f:V\to\\{0,1\\}$ is said to be friendly if it is balanced.

######  Definition 2.6.

Let ${\mathcal{D}}_{n}$ be the set of all digraphs on $n$ vertices. We will
define ${\mathcal{T}}_{n}$ as the subset of ${\mathcal{D}}_{n}$ that consists
of all digon-free digraphs, where a digon is a two cycle on a digraph.

######  Definition 2.7.

Let $D\in{\mathcal{T}}_{n}$ with $D=(V,A)$. Let $f:V\to\\{0,1\\}$ be a
friendly labeling of the vertex set $V$ of $D$. Let $g:A\to\\{-1,0,1\\}$ be an
induced labeling of the arcs of $D$ such that for any $i,j\in\\{-1,0,1\\}$,
$-1\leq|g^{-1}(i)|-|g^{-1}(j)|\leq 1$. Such a labeling is called a
$(2,3)$-cordial labeling, and a digraph $D\in{\mathcal{T}}_{n}$ that can
possess a $(2,3)$-cordial labeling will be called a $(2,3)$-cordial digraph.

######  Definition 2.8.

Let $D=(V,A)$ be a digraph with vertex labelling $f:V\to\\{0,1\\}$ and with
induced arc labelling $g:A\to\\{-1,0,1,\\}$. Define $\Gamma_{f,g}$ to be the
real triple $\Gamma_{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,0,1)$-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)$.

######  Lemma 2.1.

Let $D\in{\mathcal{T}}_{n}$ with vertex labeling $f$ and induced arc labeling
$g$. Let $\Gamma_{f,g}(D)=(\alpha,\beta,\gamma)$. Then

  1. 1.

$\Gamma_{f,g}(D^{r})=(\beta,\alpha,\gamma)$.

  2. 2.

$\Gamma_{\overline{f},\overline{g}}(D)=(\beta,\alpha,\gamma)$, and

  3. 3.

$\Gamma_{\overline{f},\overline{g}}(D^{R})=\Gamma_{f,g}(D).$

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.

Also in this article we will study when undirected graphs can have their arcs
given an orientation such that the resulting graph is $(2,3)-$cordial. We
finish this section with a couple of definitions for that.

######  Definition 2.9.

Define ${\mathcal{G}}_{n}$ to be the set of all simple, undirected, connected
graphs. We say $G\in{\mathcal{G}}_{n}$ has vertex set $V$ and edge set $E$ and
denote it by $G=(V,E).$

######  Definition 2.10.

Let $G\in{\mathcal{G}}_{n}$. An orientation of $G$ is a digraph $D(G)$ whose
vertex set is the same as the vertex set of $G$ and whose arc set consists of
the same number of arcs as the number of edges of $G$ such that given an edge
$\\{u,v\\}$ of $G$, either $\overrightarrow{uv}$ or $\overrightarrow{vu}$ is
an arc of $D(G)$ but not both, so that $D(G)$ is digon free. A graph $G$ is
said to be $(2,3)$-orientable if there exists and orientation of $G$, $D(G)$,
that is $(2,3)$-cordial.

##  3 Resolution of Two Conjectures

We begin with the first conjecture.

Conjecture 1[1, Conjecture 4.1]: Every orientation of every path is (2,3)
cordial except for a path with four vertices.

The orientation in Figure 1 of the ten path has no cordial labeling.

Figure 1:

We used the following brute force algorithm to test to see if a certain arc
orientation is cordial on a friendly labeling of a graph.

Data: Arcs, Verticies

Result: Determine if an orientation is cordial on a path

for  _arc in Arcs_ do

current = first vertex

next = second vertex

if  _arc is left_ then

edgeLabel = current - next

end if

else

edgeLabel = current - next

end if

store edge label

current = next

next = next vertex

end for

if  _edge labels are cordial_ then

return it is cordial

end if

In investigating the conjecture we had to test every possible friendly
labeling and arc orientation on ten vertices. If we let $n$ denote the number
of vertices on the path, then checking every possible friendly labeling
against every arc set has complexity of $O(2^{k})$. As a slight optimization
by Lemma 2.1 with out loss of generality we can fix the first arc and the
first label and still account for all cases up to isomorphism. That means
there will be $2^{n-2}$ arc orientations to test. In calculating all arc
orientations of the ten path we found the only orientation that is not
$(2,3)-$coridal is the one in figure 1. The next known case of a non
$(2,3)-$orientable path is one on 22 vertices with the same alternating arc
structure.

Conjecture 2[1, Conjecture2.3]: Every tree of max degree $3$ is
$(2,3)-$orientable.

Figure 2:

Figure 2 is a counter example. Though easily proved with a computer by a
similar argument as on the one above, we will prove by cases.

###### Proof.

First note that the value of $\gamma$ in a vertex labeling of the graph does
not depend on arc orientation. Thus we show that there does not exist a
friendly labeling on the vertex set of the graph that induces an edge labeling
of $\gamma=3$, by only considering vertex labelings on the undirected graph.
We will separate our graph into a right and left subgraph and then connect
them

Figure 3: Left and Right Subgraph

Let $x$ be the number of vertices labeled $1$ on one subgraph in a friendly
labeling of the whole graph. In order for the graph to be cordial $x$ cannot
be $4$ or $5$ since this would make $\gamma>3$ on the entire graph. Therefore
$x$ also cannot be $0$ or $1$ since that would mean $x$ would be too large on
the other sub graph. Thus we must have $x=2$ on one subgraph $x=3$ on the
other subgraph.

Given these constraints it is not possible to have a sub graph such that
$\gamma=0$, since there is no way to label two of the vertices on a subgraph
without having at least two vertices of the other label connected. This means
we do not need to account for the case when $\gamma=3$ on a subgraph, since
the other subgraph cannot have $\gamma=0$. Now we will consider two cases.

010100001110010
Figure 4: All $\gamma=2$ subgraph labelings 001111001110110
Figure 5: All $\gamma=1$ subgraph labelings

Case 1. With out loss of generality let the left subgraph have $\gamma=1$,
$x=2$ and the right subgraph have $\gamma=2$, $x=3$. This would mean we would
need to connect the subgraphs such that the connecting edge will not be
labeled $0$. Considering all cases we see that there is no way to connect the
two subgraphs to make the full graph without $\gamma=4$ on the full graph.
Case 2. With out loss of generality let the left subgraph have $\gamma=1$,
$x=2$, and the right subgraph have $\gamma=1$, $x=3$. This would mean we need
to find a way to connect the two subgraphs such that the connecting edge is
labeled 0. Considering all cases shows that this is not possible. ∎

The structure of the proof leads to the following theorem.

######  Theorem 3.1.

Let $G\in{\mathcal{G}}_{n}$. We define $\Lambda(G)$ to be the number of edges,
$uv$ such that vertices $u$ and $v$ have the same label for a given friendly
labeling on $G$. $G$ is $(2,3)$-orientable if and only if there exsits a
friendly vertex labling on $G$ such that
$\Lambda(G)=\left\lceil\frac{1}{3}|E|\right\rceil$ or
$\Lambda(G)=\left\lfloor\frac{1}{3}|E|\right\rfloor$, where $|E|$ is the
cardinality of the edge set of $G$

###### Proof.

Suppose $G$ satisfies $\Lambda(G)=\left\lceil\frac{1}{3}|E|\right\rceil$ or
$\Lambda(G)=\left\lfloor\frac{1}{3}|E|\right\rfloor$. This would mean about
$\frac{2}{3}$ of the edges are connected by vertices of different labels, and
therefore arcs may be assigned such that $G$ is $(2,3)-$cordial. If $G$ is
$(2,3)-$cordial, then clearly $G$ has a friendly labeling that satisfies the
above conditions. ∎

Though fairly intuitive we will now use theorem 3.1 to show two more results
that stem from it in the following section.

##  4 Theorem 3.1 applied.

######  Theorem 4.1.

The Petersen Graph, Figure 6, is not (2,3) -orientable.

###### Proof.

By Theorem 3.1 only need to show that there is no friendly labeling such that
one third of the edges are connected with the same label of the vertex. Again
let $x$ be the number of vertices labeled 1. We will start by dividing the
Petersen graph into two subgraphs and then connect them.

Figure 6: The Petersen Graph Figure 7: Two Subgraphs of the Petersen Graph

With out loss of generality the only way for our friendly label to be cordial
we must have one sub graph have $x=2$, and have $x=3$ on the other. The case
when either sub graph has $x\geq 4$ of a certain label would result in
$\gamma$ being too large. Let us first consider the outer subgraph letting
$x=3$ for this subgraph.

1101000111
Figure 8: $\gamma=1,\gamma=3$

There are two cases as shown in Figure 9, up to isomorphism. $\gamma=2$ is not
possible since there is no way to label two 0’s and two 1’s without the third
1 connecting to another vertex labeled one. This means we need to connect the
star sub graph such exactly two or exactly four more edges with zero are
produced.

1100010100
Figure 9: $\gamma=1,\gamma=3$

Figure 8 represents all labelings of the inner subgraph up to isomorphism,
with $\gamma=1$ or $\gamma=3$ possible on the subgraph. Upon inspection there
is no possible way to connect any rotation of the inner sub graph with either
of the outer sub graphs such that $\gamma=5$ for the resulting Petersen graph.
Therefore by Theorem 4.1 the Petersen graph is not $(2,3)$ cordial. ∎

One more example shows how this theorem proved useful in proving an upper
bound on the size of the edge set for any graph to be $(2,3)$-orientable. For
work on the upper bounds for other graph labelings see [6].

######  Theorem 4.2.

Given a directed graph $G=(V,E)$ with vertex set $V$ and $n=|V|$ with $n\geq
6$, and edge set $E$. The maximum size of $E$ such that $G$ is $(2,3)$
orientable for any given $n$ is

$\displaystyle|E|_{max}$ $\displaystyle=\displaystyle{n\choose
2}-Z+\left\lceil\frac{1}{2}\left(\displaystyle{n\choose
2}-Z\right)\right\rceil$ (1) $\displaystyle Z$
$\displaystyle=\displaystyle{\lceil\frac{n}{2}\rceil\choose
2}+\displaystyle{\lfloor\frac{n}{2}\rfloor\choose 2}.$ (2)

000111 Figure 10: A complete graph. Dashed Lines represent edges labeled zero
regardless of arc orientation

###### Proof.

It can be shown, see [2], that any tournament with $n\leq 5$ vertices is
$(2,3)$-cordial, save for the case when $n=4$. Thus we begin with a complete
graph with $n\geq 6$. Recall that the number of vertices on a complete graph
is $n\choose 2$. Thus $Z$ is the number of edges in two cliques comprised of
the the subgraph of the vertices labeled $0$ and the vertices labeled $1$. In
this way $Z$ counts the number of edges labeled zero regardless of arc
orientation. If $n$ is even that will mean that $Z=2{\frac{n}{2}\choose 2}$.
If $n$ is odd then $Z$ is as above. This also implies there are ${n\choose
2}-Z$ edges that cannot be labeled zero.

For every complete graph with $n\geq 6$ vertices $Z>1/3{n\choose 2}$. By
Theorem 3.1 this is too many edges to be $(2,3)-$orientable. The number edges
labeled $0$ must be balanced with the number of edges labeled $1$ and $-1$,
and the number of edges labeled $1$ or $-1$ is $1/2({n\choose 2}-Z)$. Thus the
upper bound on the number of edges a graph on $n$ vertices can have and be
$(2,3)-$orientable is as in equation 2. ∎

## References

  * [1] L. B. Beasley, Cordial Digraphs, In Press.
  * [2] L. B. Beasley, M. A. Santana, J. M. Mousley and D.E. Brown, (2,3)-Cordial Digraphs, Preprint.
  * [3] I. Cahit, Cordial graphs: A weaker version of graceful and harmonious graphs, Ars Comb. 23(1987) 201-208.
  * [4] M. Hovey, A-cordial graphs, Discrete Math. 93 (1991) 183-194.
  * [5] E Salehi, PC-labelling of a graph and its PC-set, Bull. Ins.t Comb. Appl., 58(2010) 112-121.
  * [6] M. A. Seoud and M. A. Salim, Upper Bounds of Four Types of Graph Labelings, Ars Combinatoria, 127(2016) 271-278
  * [7] Sinah Deepa, Kuar Jaspreet, Full friendly index set -I Discrete Applied Mathematics 161 (2013) 1262- 1274.
  * [8] O. Penchenik, J. Wise, Generalized Graph Cordiality Discussiones Mathematicae Graph Theory 32 (2012) 557–567