# The Cordiality Game and the Game Cordiality Number

Elliot Krop  Elliot Krop<EMAIL_ADDRESS>,  Aryan Mittal  Aryan
Mittal<EMAIL_ADDRESS>and  Michael C. Wigal  Michael Wigal (
<EMAIL_ADDRESS>Department of Mathematics, Clayton State University
Georgia Institute of Technology  Department of Mathematics, University of
Illinois Urbana-Champaign

###### Abstract.

The _cordiality game_ is played on a graph $G$ by two players, Admirable (A)
and Impish (I), who take turns selecting  unlabeled vertices of $G$. Admirable
labels the selected vertices by $0$ and Impish by $1$, and the resulting label
on any edge is the sum modulo $2$ of the labels of the vertices incident to
that edge. The two players have opposite goals: Admirable attempts to minimize
the number of edges with different labels as much as possible while Impish
attempts to maximize this number. When both Admirable and Impish play their
optimal games, we define the _game cordiality number_ , $c_{g}(G)$, as the
absolute difference between the number of edges labeled zero and one. Let
$P_{n}$ be the path on $n$ vertices. We show $c_{g}(P_{n})\leq\frac{n-3}{3}$
when $n\equiv 0\pmod{3}$, $c_{g}(P_{n})\leq\frac{n-1}{3}$ when $n\equiv
1\pmod{3}$, and $c_{g}(P_{n})\leq\frac{n+1}{3}$ when $n\equiv 2\pmod{3}$.
Furthermore, we show a similar bound, $c_{g}(T)\leq\frac{|T|}{2}$ holds for
any tree $T$.
2020 Mathematics Subject Classification: 05C57, 05C78
Keywords: cordial labeling, cordiality game, game cordiality number, trees

##  1\. Introduction and Definitions

It is natural to study combinatorial functions under the regime of two-person
games, often presenting new perspective s to old problems. One such example is
the classic cops and robbers formulation of tree-width [24]. More examples
include game chromatic number, see [1] and [25], and the more recent game
domination number [3], which has bloomed into numerous publications, of which
we only list a few, e.g., [4, 15, 17], and the monograph [2]. For more
examples of graph-theoretic games, see the extended bibliography [11] for more
references.

With this in mind, we define a new game to study a simple “algebraic balance”
in graphs, which is motivated from the following definition. A graph $G$ is
_cordial_ if there exists a labeling of the vertices of $G$ by $0$ and $1$,
where labels on edges are defined as the sum of incident vertex labels modulo
$2$ such that:

  * •

the absolute difference in the number of vertices labeled $0$ and $1$ is no
more than one;

  * •

the absolute difference in the number of edges labeled $0$ and $1$ is no more
than one.

In other words, a graph is cordial, if there exists a bipartition of its
vertex set, such that the size of each part is
$\left\lceil|V(G)|/2\right\rceil$ or $\left\lfloor|V(G)|/2\right\rfloor$, and
the number of edges that goes across the cut induced by the bipartition is
either $\left\lceil|E(G)|/2\right\rceil$ or
$\left\lfloor|E(G)|/2\right\rfloor$. Cordial labelings were first defined in
[6] and extended to $k$-cordial labelings in [16], which includes several
difficult and outstanding problems. One particular simple and natural problem
is the $3$-cordial conjecture.

A graph $G$ is $3$-cordial, if there exists a vertex labeling of $G$
satisfying the following two conditions:

  * •

The vertices are labeled by the integers $0,1,$ and $2$ such that for any
integer in $\\{0,1,2\\}$, there is at most one more vertex labeled by one of
the integers than of vertices labeled by any other fixed integer.

  * •

If for any edge, the label on that edge is found by summing its incident
vertices modulo $3$, then there is at most one more edge labeled by one of the
integers than of edges labeled by a different fixed integer.

######  Conjecture 1.1 (Hovey [16]).

All graphs are $3$-cordial.

We know of no progress made on this problem in the last thirty years. Some
examples of other extensions and variants of cordiality problems from [16] can
be seen in [8, 9, 10, 19, 20].

Let $G=(V,E)$ be a graph. The _cordiality game_ is played on $G$ by two
players, Admirable and Impish, who take turns selecting the  unlabeled
vertices of $G$. Admirable labels selected vertices by $0$ and Impish labels
selected vertices by $1$. The labels on edges are then determined by the sum
of incident vertex labels modulo $2$. Admirable’s goal is to produce a
labeling of $E$ with the minimum number of different labels while Impish
attempts to produce the labels of $E$ with the maximum number of different
labels. In other words, after all the vertices are labeled, if we let $e_{0}$
be the number of edges labeled by $0$ and $e_{1}$ be the number of edges
labeled by $1$, then we define the _discrepancy_ to be $d=|e_{1}-e_{0}|$. Then
Admirable attempts to minimize $d$ and Impish attempts to maximize $d$. Note
at the end of the game, the vertex labelings induce a balanced bipartition of
the graph.

We define the _game cordiality number_ , $c_{g}(G)$, to be the value of $d$
when both players play optimally. Further, to prove our claimed bounds, we
create a variant of the cordiality game where Impish starts rather than
Admirable. In this case, the discrepancy, assuming optimal play of both
competitors, is denoted $c_{g}^{\prime}(G)$, which we call the Impish-starts
game cordiality number. Finally, consider a further variant of the cordiality
game, in which Impish starts and may pass one time during play, so that
Admirable moves twice consecutively at some point in the game. For this game,
the discrepancy, assuming optimal play of both parties, is denoted
$c_{g}^{*}(G)$. Note that $c_{g}^{\prime}(G)\leq c_{g}^{*}(G)$, as Impish may
always choose a strategy that avoids passing  his turn.

Our cordiality game can be interpreted as a classic positional game under a
small adjustment. First introduced by Chvátal and Erdős [7], the Maker-Breaker
game has received significant attention prior in the literature, e.g., see
[14, 18]. A family ${\mathcal{F}}$ of winning subsets of some set $X$ is known
to both players prior. The players alternate between selecting  previously
unselected elements. At the end, Maker wins if he obtains a set of
${\mathcal{F}}$, otherwise Breaker wins. For some fixed integer $k\geq 0$, let
${\mathcal{F}}_{k}$ be the family of vertex sets which are parts of a balanced
bipartition of discrepancy at most $k$. Note then for the cordiality game,
Maker would play the role of Admirable, Breaker taking the role of Impish.
Clearly, setting $k=c_{g}(G)$, a winning strategy for one game translates to
the other.

In Section $2$, we present an upper bound for $c_{g}(P_{n})$ when $P_{n}$ is a
path on $n$ vertices. We  prove

$c_{g}(P_{n})\leq\begin{cases}\frac{n-3}{3}&n\equiv 0\pmod{3}\\\
\frac{n-1}{3}&n\equiv 1\pmod{3}\\\ \frac{n+1}{3}&n\equiv 2\pmod{3}\\\
\end{cases}$

In Section $3$, we show that for any tree $T$, $c_{g}(T)\leq\frac{1}{2}n$. In
Section $4$, we introduce a variant of the cordiality game and end with some
open questions.

We finish this section with some notation. For a graph $G$, we let $\phi$
denote the _cut function_ for $G$. That is, for all $S\subseteq V(G)$,
$\phi(S)=|\\{uv\in E(G):u\in S,v\not\in S\\}|$. We let  $\text{dis}(S)$ denote
the discrepancy of the cut induced by $S$, where
$\text{dis}(S)=\phi(S)-(|E(G)|-\phi(S))=2\phi(S)-|E(G)|$. Note then the
objective of the cordiality game is  $\text{dis}(S)$ where $S$ is the set of
vertices labeled 0 or 1.  Furthermore, we note the parity of $\text{dis}(S)$
is always the same as that of $|E(G)|$. A _balanced partition_ of a graph $G$
is a partition of $V(G)$ into two sets, say $S_{1}$ and $S_{2}$, such that
$||S_{1}|-|S_{2}||\leq 1$.

##  2\. Paths

The problem of finding the exact value of $c_{g}(P_{n})$ is surprisingly
involved. We begin with calculating the game cordiality number for small
paths.

######  Lemma 2.1.

We have the following:

  1. i.

$c_{g}(P_{3})=c^{\prime}_{g}(P_{3})=c_{g}^{*}(P_{3})=0$,

  2. ii.

$c_{g}(P_{4})=c^{\prime}_{g}(P_{4})=c_{g}^{*}(P_{4})=1$,

  3. iii.

$c_{g}(P_{5})=c^{\prime}_{g}(P_{5})=c_{g}^{*}(P_{5})\leq 2$,

  4. iv.

$c_{g}(P_{6})=c^{\prime}_{g}(P_{6})=c^{*}_{g}(P_{6})=1$.

###### Proof.

Let $P_{n}=v_{1}v_{2}\cdots v_{n}$ and let $S,\overline{S}$ be a balanced
bipartition of $V(P_{n})$.

In the case $n=3$,  $\text{dis}(S)$ is always even. As $|E(P_{3})|=2$,
$\\{v_{2}\\},\\{v_{1},v_{3}\\}$ is the only bipartition that achieves
discrepancy greater than 0. Thus if Admirable plays $v_{2}$ first, this
guarantees a bipartition of discrepancy zero. In the case Impish plays first,
Admirable just needs to avoid playing $v_{2}$. Thus we may conclude
$c_{g}(P_{3})=c^{\prime}_{g}(P_{3})=c_{g}^{*}(P_{3})=0$.

When $n=4$,  $\text{dis}(S)$ is always odd. By observation,
$\\{v_{1},v_{3}\\},\\{v_{2},v_{4}\\}$ is the only balanced bipartition that
achieves discrepancy greater than 1. Clearly if Admirable has a strategy of
playing once from each set, regardless of who starts, this guarantees a
resulting bipartition of discrepancy 1. Note as  $\text{dis}(S)\geq 0$ and
odd, we may conclude $c_{g}(P_{4})=c_{g}^{\prime}(P_{4})=c_{g}^{*}(P_{4})=1$.

In the case $n=5$,  $\text{dis}(S)$ is always even. As $|E(P_{5})|=4$, the
only balanced bipartition that achieves discrepancy greater than 2 is
$\\{v_{1},v_{3},v_{5}\\},\\{v_{2},v_{4}\\}$. Again if Admirable takes a
strategy of playing once from each set, this is a strategy guaranteeing
$c_{g}(P_{5})=c^{\prime}_{g}(P_{5})=c^{*}_{g}(P_{5})\leq 2$.

We now work towards understanding our game variants on $P_{6}$. By parity,
$\text{dis}(S)$ is odd and  $\text{dis}(S)\geq 1$ for any balanced bipartition
$S$,$\overline{S}$. There are only two choices for $S$ that achieve
discrepancy 5, namely $\\{v_{1},v_{3},v_{5}\\}$ and its complement
$\\{v_{2},v_{4},v_{6}\\}$. We now observe the balanced bipartitions which
achieve discrepancy 3. To do so, we would either need exactly 1 or 4 edges
crossing the cut induced by the bipartition. The former case only occurs with
$S$ being $\\{v_{1},v_{2},v_{3}\\}$ or $\\{v_{4},v_{5},v_{6}\\}$. The latter
case occurs only with $S$ being
$\\{v_{2},v_{3},v_{5}\\},\\{v_{2},v_{4},v_{5}\\},\\{v_{1},v_{4},v_{6}\\}$, or
$\\{v_{1},v_{3},v_{6}\\}$. Note then for Admirable to obtain discrepancy 1 in
the cordiality game, there is in total 8 “bad labelings” to avoid.  We list
them as follows.

$\displaystyle\\{v_{1},v_{3},v_{5}\\},\;\;\;\\{v_{2},v_{4},v_{6}\\},\>\>\;\\{v_{1},v_{2},v_{3}\\},\;\;\;\;\\{v_{4},v_{5},v_{6}\\},$
$\displaystyle\\{v_{2},v_{3},v_{5}\\},\;\;\;\\{v_{2},v_{4},v_{5}\\},\;\;\;\\{v_{1},v_{4},v_{6}\\},\;\;\;\\{v_{1},v_{3},v_{6}\\}.$

We now give a strategy for Admirable which guarantees a balanced cut of
discrepancy 1, i.e., $c_{g}(P_{6})=1$. We may assume Admirable plays on
$v_{1}$ first. Note then there is only four bad labelings for Admirable to
avoid now, $\\{v_{1},v_{3},v_{5}\\}$, $\\{v_{1},v_{2},v_{3}\\}$,
$\\{v_{1},v_{4},v_{6}\\}$, or $\\{v_{1},v_{3},v_{6}\\}$. Note $v_{3}$ is in
three of these bad sets. As Admirable plays first and $|P_{6}|$ is even, we
may suppose Admirable never plays $v_{3}$. Thus to avoid the final bad set
$\\{v_{1},v_{4},v_{6}\\}$, on Admirable’s second move, we may assume Admirable
plays on either $v_{2}$ or $v_{5}$. This guarantees that Admirable labels a
set $S$ such that  $\text{dis}(S)=1$.

We now give a strategy for Admirable in which Impish plays first. In the case
where Impish is also allowed to pass  his turn to Admirable once, the analysis
is almost the same which we note at the end. By symmetry, we may suppose
Impish plays $v_{1}$,$v_{2}$ or $v_{3}$.

If Impish plays on $\\{v_{1},v_{3}\\}$ on  his first move, then Admirable
plays $\\{v_{1},v_{3}\\}$ for  his first move as well. Note then the only bad
labeling for Admirable to avoid now is $\\{v_{1},v_{4},v_{6}\\}$ or
$\\{v_{2},v_{3},v_{5}\\}$ depending on  his first move choice. This can
clearly be achieved. If Impish plays $v_{2}$, then Admirable plays $v_{5}$.
Note then the only bad labelings to avoid are $\\{v_{4},v_{5},v_{6}\\}$ and
$\\{v_{1},v_{3},v_{5}\\}$. To avoid these, if Impish plays on
$\\{v_{4},v_{6}\\}$ on  his second move, then Admirable plays on
$\\{v_{4},v_{6}\\}$. In a similar manner, if Impish plays on
$\\{v_{1},v_{3}\\}$ on  his second move, then Admirable plays on
$\\{v_{1},v_{3}\\}$. If Impish chooses to pass on  his second turn, Admirable
simply plays on $\\{v_{1},v_{3}\\}$ on  his second move and then
$\\{v_{4},v_{6}\\}$ on  his third move. Thus we may conclude
$c_{g}^{\prime}(P_{6})=c_{g}^{*}(P_{6})=1$.

∎

We now prove an upper bound for all paths.

######  Theorem 2.2.

For any integer $n\geq 3$,

$c_{g}(P_{n})\leq\begin{cases}\frac{n-3}{3}&n\equiv 0\pmod{3}\\\
\frac{n-1}{3}&n\equiv 1\pmod{3}\\\ \frac{n+1}{3}&n\equiv 2\pmod{3}\\\
\end{cases}$

###### Proof.

Let $P_{n}=v_{1}v_{2}\cdots v_{n}$. We now proceed by induction on $n$. By
Lemma 2.1, we may suppose that the theorem holds for all paths of order less
than $n>6$ and consider $P_{n}$. We describe a strategy for Admirable which,
regardless of the moves Impish makes, will produce the claimed upper bounds.

Let $P$ be the subpath of $P_{n}$ induced on $v_{1},\dots,v_{n-6}$ and
$P^{\prime}$ be the $P_{6}$ subpath of $P$ induced by $v_{n-5},\dots,v_{n}$.
We will prove the inequality

$c_{g}(P_{n})\leq\begin{cases}2\lfloor\frac{n}{6}\rfloor-1&n\equiv
0\pmod{6}\\\ 2\lfloor\frac{n}{6}\rfloor&n\equiv 1,3\pmod{6}\\\
2\lfloor\frac{n}{6}\rfloor+1&n\equiv 2,4\pmod{6}\\\
2\lfloor\frac{n}{6}\rfloor+2&n\equiv 5\pmod{6}\\\ \end{cases}$

which can be easily reduced to the claimed statement.

Suppose $n$ is odd. Admirable begins by playing an optimal game on $P$. From
that point, Admirable follows Impish between $P$ and $P^{\prime}$. If Impish
plays on $P$, Admirable continues playing an optimal game on $P$. If Impish
plays on $P^{\prime}$, then Admirable follows with a next optimal move on
$P^{\prime}$. This strategy results in an Impish-starts game on $P^{\prime}$
and an Admirable-starts game on $P$. Recall by Lemma 2.1,
$c^{\prime}_{g}(P^{\prime})=c^{\prime}_{g}(P_{6})=1$. We apply the induction
hypothesis on $P$ and consider that the edge between $P$ and $P^{\prime}$,
$v_{n-6}v_{n-5}$, as an unknown label. Since $n-6\pmod{6}=n\pmod{6}$, the
values in the proposed upper bound of $c_{g}(P_{n})$ follow s by adding $2$ to
the bounds for $c_{g}(P_{n-6})$.

Next, we suppose that $n$ is even. The strategy for Admirable is the same as
the previous case. Admirable begins by playing an optimal game on $P$. From
that point, Admirable follows Impish between $P$ and $P^{\prime}$. If Impish
plays on $P$, Admirable continues playing an optimal game on $P$. If Impish
plays on $P^{\prime}$, Admirable follows with a next optimal move on
$P^{\prime}$. Due to the parity of $n$ in this case, this strategy allows for
several variants of the cordiality game. If Impish completes a game on $P$
before moving to $P^{\prime}$, then the game on $P^{\prime}$ becomes an
Admirable-starts game. If Impish plays $P^{\prime}$ before completing the game
on $P$, then the game on $P^{\prime}$ becomes an Impish-starts game. If Impish
does not finish the game on $P^{\prime}$, returns to $P$, and completes the
game there, then Admirable must make the next move on $P^{\prime}$, which is
equivalent to playing an Impish-starts game on $P^{\prime}$ where Impish may
pass once. Regardless of Impish strategy, by Lemma 2.1,
$c_{g}(P_{6})=c^{\prime}_{g}(P_{6})=c^{*}_{g}(P_{6})=1$. Thus by induction on
$P$, and treating $v_{n-6}v_{n-5}$ as an unknown label, this produces the
claimed upper bounds for $c_{g}(P_{n})$ as before. ∎

For a lower bound, our methods are ineffective, and so from some empirical
considerations ($n\leq 12$), we ask the following speculative question.

######  Open question 1.

Does $c_{g}(P_{n})$ assume the values $0$ and $1$ for infinitely many integers
$n$?

##  3\. Trees

In Theorem 2.2, if our input path $P_{n}$ is long, i.e. $n\geq 6$, we break
the instance into two smaller paths, $P_{n-6}$ and $P_{6}$, and then induct
with a strategy of Admirable following Impish. There are challenges to
extending this proof strategy to an arbitrary tree $T$. A subtree $B$ of a
tree $T$ is a _branch_ , if there exists a subtree $T^{\prime}$ of $T$ such
that $B\cup T^{\prime}=T$ and $|V(T^{\prime})\cap V(B)|=1$. Ideally, we would
like to find a small branch of constant size to break the instance into two
smaller trees. If we do so naively, we no longer have control on what this
branch looks like, in particular, the branch may be of odd order. Using the
strategy of Admirable following Impish, Impish may play the odd ordered branch
entirely with some vertices still unlabeled in the remainder of the tree,
which would lead to Admirable playing twice in-a-row on the remainder of the
tree. Thus, to avoid this potential difficulty in analysis, we consider how to
remove a branch that is small enough to label, yet also of even order.

######  Theorem 3.1.

For any tree  $T$ of order $n$,

$c_{g}(T)\leq\frac{1}{2}n.$

###### Proof.

We proceed by induction on the order $n$. Note that the theorem holds
trivially for trees of order $1,2$, and $3$, so we suppose the statement is
true for all trees of order less than $n>3$ and consider a tree $T$ of order
$n$.

We describe Admirable’s strategies and calculate discrepancies for various
possible branches of $T$. We will then  show that our bound holds in every
instance.  Let $B$ be a branch of $T$, let $T^{\prime}$ be a subtree of $T$
such that $B\cup T^{\prime}=T$ and $|V(T^{\prime})\cap V(B)|=1$, and let $v$
be the vertex which is both in $B$ and $T^{\prime}$.  Finally, we let $S$ be
the subgraph of $T$ induced by the vertices of $B-v$.

Throughout the proof, we will assume Admirable begins playing an optimal game
on $T^{\prime}$, and then following Impish between $T^{\prime}$ and $S$
depending on where Impish plays. In the case Impish played on $T^{\prime}$,
and $T^{\prime}$ has no remaining unlabeled vertices, Admirable will begin
playing on $S$ if possible. We also will choose $B$ such that $|S|$ is always
even. We remark that as $|T^{\prime}|+|S|=|T|$, we have

  * •

If $|T^{\prime}|$ is even, then the game on $S$ is either an Admirable-start
game or an Impish-start game where Impish may pass up to one time during play.

  * •

If $|T^{\prime}|$ is odd, then the game on $S$ is an Impish-start game.

Note in the case $|T^{\prime}|$ is even, $S$ is an Admirable-start game if and
only if every vertex of $T^{\prime}$ has been previously played.

######  Case 1.

Branch $B$ isomorphic to $P_{5}$ with end-vertex $v$ in $T^{\prime}$

If $T$ contains a branch isomorphic to $P_{5}=(v,v_{1},v_{2},v_{3},v_{4})$,
where $\deg(v_{i})=2$ for $i=1,2,3$ and $\deg(v_{4})=1$, in $T$, then we
define $T^{\prime}=T-\\{v_{1},\dots,v_{4}\\}$ and let $S$ be the subgraph of
$T$ induced by $v_{1},v_{2},v_{3},v_{4}$. By Lemma 2.1,
$c_{g}(P_{4})=c^{\prime}_{g}(P_{4})=c^{*}_{g}(P_{4})=1$, we can apply the
induction hypothesis to $T^{\prime}$ and consider the edge between
$T^{\prime}$ and $S$ as one with an unknown label, to produce the bound

$c_{g}(T)\leq c_{g}(T^{\prime})+2\leq\frac{1}{2}(n-4)+2=\frac{1}{2}n.$

######  Case 2.

Branch $B$ isomorphic to $P_{3}$ with central vertex $v$ in $T^{\prime}$.

$v$$v_{1}$$v_{2}$

Let the vertices of $B$ be labeled as the above figure, and let $S$ be the
subgraph induced by $\\{v_{1},v_{2}\\}$.  As Admirable plays first on
$T^{\prime}$, and follows Impish between $T^{\prime}$ and $S$, playing on $S$
first if and only if $T^{\prime}$ is completely labeled, the edges $vv_{1}$
and $vv_{2}$ will always have different labels. Thus the claim follows by
induction on $T^{\prime}$.

######  Case 3.

Branch $B$ isomorphic to $P_{5}=\\{v_{1},v_{2},v,v_{3},v_{4}\\}$ with vertex
$v$ in $T^{\prime}$.

$v$$v_{2}$$v_{1}$$v_{3}$$v_{4}$

Let  $B$ be labeled as the above figure and let $S$ be the subgraph induced by
$\\{v_{1},v_{2},v_{3},v_{4}\\}$. We now give strategies for Admirable  on $S$
that produces a discrepancy of  at most $2$ for the  edges induced by the
branch $B$, regardless of the value of the label on $v$. Note this occurs if
both Admirable and Impish have played on $\\{v_{2},v_{3}\\}$. To see this,
$vv_{2}$ and $vv_{3}$ must have different signs. Thus we have discrepancy at
most $2$ from edges $v_{1}v_{2}$ and $v_{3}v_{4}$.

We begin with the Admirable-start game s. We may suppose Admirable plays
$v_{2}$, and then plays on $\\{v_{1},v_{4}\\}$. This guarantees both players
played on $\\{v_{2},v_{3}\\}$.

For  an Impish-starts game,  if Impish plays on $\\{v_{2},v_{3}\\}$, then
Admirable immediately follows by playing on $\\{v_{2},v_{3}\\}$ as well. If
Impish plays on $\\{v_{1},v_{4}\\}$, then Admirable again immediately follows
by playing on $\\{v_{1},v_{4}\\}$ as well. Note this strategy is robust
against the case where Impish is also allowed to pass  his turn.

######  Case 4.

Branch $B$ is illustrated below with vertex $v$ in $T^{\prime}$.

$v$$v_{1}$$v_{2}$$v_{3}$$v_{4}$

Let  the vertices of $B$ be labeled as in the figure, and let $S$ be the
subgraph induced by $\\{v_{1},v_{2},v_{3},v_{4}\\}$.  We give a strategy for
Admirable which produces a discrepancy of at most $2$ for the edges induced by
$B$, regardless of the value of the label on $v$. Note that
$v_{4}v_{1}v_{2}v_{3}$ induce s a path, thus it is sufficient to bound the
discrepancy of the edges $v_{4}v_{1},v_{1}v_{2},v_{2}v_{3}$ by one. This is
true by Lemma 2.1.

######  Case 5.

Branch $B$ isomorphic to $P_{5}=\\{v_{1},v,v_{2},v_{3},v_{4}\\}$ with vertex
$v$ in $T^{\prime}$.

$v$$v_{1}$$v_{2}$$v_{3}$$v_{4}$

Let  the vertices of $B$ be labeled as the figure above, and let $S$ be the
subgraph induced by $\\{v_{1},v_{2},v_{3},v_{4}\\}$.  As in the prior case, we
give a strategy for Admirable on $S$ that produces a discrepancy of  at most
$2$ for $B$, regardless of the value of the label on $v$. Note this occurs if
Admirable plays once on $S_{1}=\\{v_{1},v_{2}\\}$ and once on
$S_{2}=\\{v_{3},v_{4}\\}$.

For Admirable-start games, we first play $v_{1}$ and then Admirable on  his
second move plays on $\\{v_{3},v_{4}\\}$. When Impish plays first, if Impish
plays on $S_{i}$ for $i\in\\{1,2\\}$, then Admirable follows by playing on
$S_{i}$ as well. In the case Impish is allowed to pass and does so on  his
second move, Admirable plays in a way so that he plays on both $S_{1}$ and
$S_{2}$.

######  Case 6.

Branch $B$ isomorphic to $P_{7}=\\{v_{1},v_{2},v_{3},v,v_{4},v_{5},v_{6}\\}$
with vertex $v$ in $T^{\prime}$.

$v$$v_{1}$$v_{2}$$v_{3}$$v_{4}$$v_{5}$$v_{6}$

Let  the vertices of $B$ be labeled as above and $S$ be the subgraph induced
by $\\{v_{1},v_{2},v_{3},v_{4},v_{5},v_{6}\\}$.  Again, we give a strategy for
Admirable on $S$ that produces a discrepancy of  at most $2$ for the branch
$B$, regardless of label on $v$.  To achieve this, we describe the possible
winning labelings for Admirable. In the first case, suppose both Admirable and
Impish play on $\\{v_{1},v_{4}\\}$. Conditioned on this constraint, by
inspection, the sets inducing cuts of discrepancy at most $2$ on $S$ are the
following,

$\displaystyle\\{v_{1},v_{2},v_{5}\\},\;\;\;\\{v_{1},v_{2},v_{6}\\},\;\;\;\\{v_{1},v_{3},v_{6}\\},\;\;\;\\{v_{1},v_{5},v_{6}\\},$
$\displaystyle\\{v_{2},v_{3},v_{4}\\},\;\;\;\\{v_{2},v_{4},v_{5}\\},\;\;\;\\{v_{3},v_{4},v_{5}\\},\;\;\;\\{v_{3},v_{4},v_{6}\\}.$

As the edges $vv_{1}$ and $vv_{4}$ must have different labelings, if Admirable
labels one of the above sets, this would be considered a winning labeling. Now
consider the other case, either only Admirable or Impish play on
$\\{v_{1},v_{4}\\}$. Under this assumption, Admirable must guarantee the edges
induced by $S$ have discrepancy $0$ under his labeling. By inspection, the
following are such labelings,

$\displaystyle\\{v_{1},v_{2},v_{4}\\},\;\;\;\\{v_{1},v_{4},v_{5}\\},\>\>\;\\{v_{2},v_{3},v_{6}\\},\;\;\;\;\\{v_{3},v_{5},v_{6}\\}.$

Thus, in all cases, we will give a strategy for Admirable for playing on $S$
that guarantees one of the above twelve labelings.

We first handle Admirable-start games on $S$. Admirable beings by playing
$v_{1}$. First suppose Impish does not play $v_{6}$ on their first move. Then
on Admirable’s second move, he plays $v_{6}$. For Admirable third move, he
avoids playing $v_{4}$. As Admirable played first and $|S|$ is even, this is
always possible. The possible labelings for Admirable are

$\displaystyle\\{v_{1},v_{2},v_{6}\\},\;\;\;\\{v_{1},v_{3},v_{6}\\},\;\;\;\\{v_{1},v_{5},v_{6}\\},$

all of which are one of the possible twelve winning labelings. Now suppose
Impish plays $v_{6}$ on his first move. On Admirable’s second move, they play
$v_{2}$. If Impish does not play $v_{4}$ on his second turn (or he passes),
Admirable would then play $v_{4}$, Admirable would play $v_{4}$, obtaining the
set $\\{v_{1},v_{2},v_{4}\\}$, a winning set. If Impish plays on $v_{4}$ on
his second move, Admirable would then play $v_{5}$, which would guarantee the
winning set $\\{v_{1},v_{2},v_{5}\\}$.

We now consider Impish-start games. By symmetry, we may assume Impish plays on
$\\{v_{1},v_{2},v_{3}\\}$. First suppose Impish plays $v_{1}$. Admirable would
then play $v_{3}$. If Impish does not play $v_{4}$ (or passes) for his second
move, Admirable plays $v_{4}$ for his second move. Regardless of Admirable’s
third move, he would obtain one of the following labelings,

$\displaystyle\\{v_{2},v_{3},v_{4}\\},\;\;\;\\{v_{3},v_{4},v_{5}\\},\;\;\;\\{v_{3},v_{4},v_{6}\\},$

all of which are winning. So suppose Impish plays $v_{4}$ on his second move.
From here Admirable would play $v_{6}$ on his second move. Irrespective of
Admirable’s third move, he obtains one of the following winning labelings,

$\displaystyle\\{v_{2},v_{3},v_{6}\\},\;\;\;\\{v_{3},v_{5},v_{6}\\}.$

Now suppose Impish plays $v_{2}$ on his first move. Admirable would then
follow by playing $v_{5}$. Regardless of how Impish plays (or passes),
Admirable can guarantee he labels exactly one vertex from $\\{v_{1},v_{3}\\}$
and exactly one vertex from $\\{v_{4},v_{6}\\}$. The possible labelings
Admirable may obtain are

$\displaystyle\\{v_{1},v_{4},v_{5}\\}\;\;\;\\{v_{1},v_{5},v_{6}\\}\;\;\;\\{v_{3},v_{4},v_{5}\\}\;\;\;\\{v_{3},v_{5},v_{6}\\},$

all of which are winning.

Now suppose Impish plays on $v_{3}$ for his first move, Admirable would then
follow by playing $v_{1}$. If Impish does not play $v_{5}$ or passes on their
second move, Admirable plays $v_{5}$. The possible final labels for Admirable
in this case would be

$\displaystyle\\{v_{1},v_{2},v_{5}\\}\;\;\;\\{v_{1},v_{4},v_{5}\\}\;\;\;\\{v_{1},v_{5},v_{6}\\}$

all of which are winning. If Impish plays $v_{5}$ on this second move,
Admirable would then play $v_{2}$. The possible final game states for
Admirable are

$\displaystyle\\{v_{1},v_{2},v_{6}\\}\;\;\;\\{v_{1},v_{2},v_{4}\\}$

which are both winning.

######  Case 7.

Branch $B$ is illustrated below with vertex $v$ in $T^{\prime}$.

$v$$v_{1}$$v_{2}$$v_{3}$$v_{4}$$v_{5}$$v_{6}$

Let  the vertices of $B$ be labeled as pictured above and let $S$ be the
subgraph induced by $\\{v_{1},v_{2},v_{3},v_{4},v_{5},v_{6}\\}$. Note that $S$
induces a subgraph isomorphic to $P_{6}$. By Lemma 2.1, the optimal
discrepancy was shown to be $1$ for $P_{6}$, taking into the account the edge
between $v$ and $v_{1}$ in $B$ produces a discrepancy of at most $2$.

We now finish the proof by showing  that $T$ has a branch $B$ as described as
in the prior seven cases. By Theorem 2.2, we may assume $T$ has a vertex of
degree at least three. Let $T^{\prime}$ be the tree obtained from $T$ by
suppressing all degree two vertices and let $T^{\prime\prime}$ be the tree
obtained from $T^{\prime}$ by deleting all leaves of $T^{\prime}$. Let $u\in
V(T^{\prime\prime})$ be a leaf of $T^{\prime\prime}$. Note then
$d_{T^{\prime}}(u)=d_{T}(u)\geq 3$, as $u\in V(T^{\prime})$ and $u$ was not a
leaf of $T^{\prime}$.  Thus, $u$ must be adjacent to at least two leaves in
$T^{\prime}$, as  $d_{T^{\prime\prime}}(u)\leq 1$.  Furthermore, if
$|V(T^{\prime\prime})|=1$, we have that $d_{T^{\prime\prime}}(u)=0$ and $u$ is
adjacent to at least three leaves in $T^{\prime}$.

We now observe $u$ in $T$. Let $Q_{1},\ldots,Q_{k}$ be the components of $T-u$
which are paths.  If $|V(T^{\prime\prime})|=0$, then $u$ is adjacent to at
least three leaves in $T^{\prime}$, thus $d_{T}(u)=k\geq 3$. Otherwise,
$|V(T^{\prime\prime})|>1$, $k\geq 2$, and by our choice of $u$,
$d_{T}(u)=k+1\geq 3$.

First suppose there exists $i$ such that $|Q_{i}|\geq 4$. Then there exists
some $v\in V(Q_{i})\cup\\{u\\}$ such that $v$ is the endpoint of a branch $B$
isomorphic to $P_{5}$. Thus by Case 1, we may suppose $|Q_{i}|\leq 3$ for all
$i$. By Cases 2, 3, and 6, for each $j\in\\{1,2,3\\}$, there can be at most
one $i$ such that $|Q_{i}|=j$. By Case 5, there cannot be two distinct
$i,i^{\prime}$ such that $|Q_{i}|=1$ and $|Q_{i^{\prime}}|=3$. Note this
implies $k=2$, and without loss of generality, $|Q_{1}|=2$ and either
$|Q_{2}|=1$ or $|Q_{2}|=3$. Note this implies $d_{T}(u)=3$ as well. Depending
on the order of $Q_{2}$, either Case 4 or Case 7 is applicable, thus the claim
follows.

∎

We do not believe that the upper bound in Theorem 3.1 is sharp. In fact, we
posit that paths are the worst case for the  cordiality game.

######  Conjecture 3.2.

For any tree $T$ of order $n$, $c_{g}(T)\leq c_{g}(P_{n})$.

##  4\. The Balance Game

While studying cordiality game strategies, it becomes evident that Admirable
cannot simply greedily label edges 0 or 1, as Impish can decide to “play into”
this strategy and further imbalance the edge labelings. As a curiosity, one
may wonder what happens if each player instead adopts a greedy objective of
trying to maximize the number of edges with a particular label. To consider
this proposition, we introduce a new game.

Let $G$ be a graph with vertices $V$ and edges $E$. The _balance game_ is
played in a similar fashion as the cordiality game, but with a modified
discrepancy $d$. We remove the absolute value from our previous definition of
$d$ and define the (signed) discrepancy of the balance game to be
$d=e_{1}-e_{0}$. The objectives of Admirable and Impish are still to minimize
and maximize $d$, respectively. However, these objectives can now be
interpreted as Admirable and Impish attempting to maximize the number of 0s
and 1s, respectively, in the labeling of $E$. We define the _game balance
number_ , $b_{g}(G)$, to be the value of $d$ when both players play optimally.
As in the cordiality game, this game too can be interpreted as an instance of
a Maker-Breaker game. For $k\geq 0$, let ${\mathcal{F}}_{k}$ be the family of
vertex sets $S$ such that $S$ and $V\setminus S$ is a balanced partition of
$V$ and $2\phi(S)-|E(G)|\leq k$. Again, Maker plays the role of Admirable, and
Breaker plays the role of Impish.

Notice that for any graph $G$, Admirable can choose to play according to the
optimal cordiality game strategy on $G$. This will produce a balance game
discrepancy of $\pm c_{g}(G)$, depending on whether 0s or 1s form a majority
of the edge labels. Hence, we have $b_{g}(G)\leq c_{g}(G)$. Our proof method
for paths translates to the balance game as the following theorem illustrates.

######  Theorem 4.1.

For any integer $n\geq 2$, $b_{g}(P_{n})\geq 0$.

###### Proof.

Let $P_{n}=v_{1}v_{2}\cdots v_{n}$. Note the theorem follows if $n=2$. We
proceed by induction on $n\geq 3$. Let $P$ be the subpath of $P_{n}$ induced
on $v_{1},v_{2},\dots,v_{n-2}$ and $P^{\prime}$ be the $P_{2}$ subpath of $P$
induced by $v_{n-1},v_{n}$. We present a strategy for Impish that, regardless
of the moves Admirable makes, will produce the desired bound.

If Admirable plays on $P$, Impish continues by playing the optimal game on
$P$. If Admirable plays on $P^{\prime}$, then Impish plays the remaining
vertex on $P^{\prime}$. If Admirable finishes a game on $P$ before moving to
$P^{\prime}$, Impish plays $v_{n}$. Regardless of the parity of $n$, this
results in an Admirable-starts game on $P$ and the edge $v_{n-1}v_{n}$ being
labeled 1. We apply the induction hypothesis on $P$ and consider that the edge
between $P$ and $P^{\prime}$, $v_{n-2}v_{n-1}$, has an unknown label, which
produces the claimed lower bound of 0. ∎

We are not aware of any graph that violates this lower bound. We leave as an
open question on whether there exists a graph $G$ with an accompanied
Admirable strategy which produces a negative discrepancy.

######  Open question 2.

For any graph $G$, does $b_{g}(G)\geq 0$?

As an aside, the balance game has an interesting physical interpretation
through the well-known Ising Model from statistical physics, e.g., see [12,
Section 1.4.2] for the relevant definitions. Two players assign spin states,
one assinging “up”, the other player “down”, to  the remaining unassigned
particles in alternating turns, competing over the energy of the final
configuration at game completion. Open Question 2, reinterpreted, states: does
the optimal strategy for the game keeps the Hamiltonian of the model
nonnegative (with the assumption of an external magnetic field being absent)?

The complexity of Maker-Breaker games is well-studied, see for example [5, 21,
23]. As the Maker-Breaker instances of the cordiality game and balance game
have a large amount of combinatorial structure on the associated set system,
this leads to the following natural question.

######  Open question 3.

Are the corresponding Maker-Breaker games to the cordiality and balance game
PSPACE-complete?

##  5\. Acknowledgments

We would like to thank the anonymous referee for their careful reading and
their comments improving the paper. This work was done while third author was
a graduate student at Georgia Tech and was supported by an NSF Graduate
Research Fellowship under Grant No. DGE-1650044.

## References

  * [1] T. Bartnicki, J. Grytczuk, H. A. Kierstead, and X. Zhu, The Map-Coloring Game. The American Mathematical Monthly 114 (9)(2007), 793–803.
  * [2] B. Brešar, M. A. Henning, S. Klavžar, and D. F. Rall, Domination Games Played on Graphs, Springer, Cham 2021.
  * [3] B. Brešar, S. Klavžar, and D. F. Rall, Domination game and an imagination strategy. SIAM J. Discrete Math. 24 (2010), 979–991.
  * [4] Cs. Bujtás, M. A. Henning, and Z. Tuza, Transversal game on hypergraphs and the $\frac{3}{4}$-conjecture on the total domination game. SIAM J. Discrete Math. 30 (2016), 1830–1847.
  * [5] J. M. Byskov, Maker-maker and maker-breaker games are PSPACE-complete, Technical Report RS-04-14, BRICS, Department of Computer Science, Aarhus University (2004).
  * [6] I. Cahit, Cordial graphs: a weaker version of graceful and harmonious graphs, Ars Combin. 23 (1987) 201–207.
  * [7] V. Chvátal and P. Erdős, Biased positional games, Ann. Discrete Math., 2 (1978) 221–229.
  * [8] S. Cichacz, On some graph-cordial Abelian groups, Discrete Math. 345(5) (2022) 112815.
  * [9] S. Cichacz, A. Görlich, Z. Tuza, Cordial labeling of hypertrees, Discrete Math. 313 (22) (2013) 2518–2524.
  * [10] K. Driscoll, E. Krop, M. Nguyen, All trees are six-cordial, Electron. J. Graph Theory Appl. 5(1) (2017) 21-35.
  * [11] A. Fraenkel, Combinatorial Games: Selected Bibliography with a Succinct Gourmet Introduction Electron. J. Combin., Dynamic Surveys, DS2: Aug 9, (2012).
  * [12] S. Friedli and Y. Velenik, Statistical mechanics of lattice systems: a concrete mathematical introduction, Cambridge University Press 2017.
  * [13] R.L. Graham and N.J.A. Sloane, On additive bases and harmonious graphs, SIAM J. Algebraic Discrete Methods 1 (1980) 382–404.
  * [14] D. Hefetz, M. Krivelevich, M. Stojaković, and T. Szabó, Positional Games (Oberwolfach Seminars), Birkhauser 2014.
  * [15] M. A. Henning and W. B. Kinnersley, Domination game: A proof of the $\frac{3}{5}$-conjecture for graphs with minimum degree at least two. SIAM J. Discrete Math. 30 (2016), 20–35.
  * [16] M. Hovey, $A$-cordial graphs, Discrete Mathematics, 93 (1991) 183–194.
  * [17] W. B. Kinnersley, D. B. West, and R. Zamani, Extremal problems for game domination number. SIAM J. Discrete Math. 27 (2013), 2090–2107.
  * [18] M. Krivelevich, Positional Games, in: Proceedings of the International Congress of Mathematicians (ICM), 4 (2014) 355–379.
  * [19] R. Patrias and O. Pechenik Path-cordial abelian groups, Australasian Journal of Combinatorics 80 (1) (2021) 157–166.
  * [20] O. Pechenik and J. Wise, Generalized graph cordiality, Discussiones Mathematicae Graph Theory 32 (2012) 557–567.
  * [21] M. L. Rahman, and T Watson, 6-uniform Maker-Breaker game is PSPACE-complete, Combinatorica, (2023) 1–18.
  * [22] A. Rosa, On certain valuations of the vertices of a graph, Theory of Graphs (Internat. Sympos., Rome, 1966), New York: Gordon and Breach, (1967) 349–355.
  * [23] J. Schaefer. On the complexity of some two-person perfect information games. J. Comput. Syst. Sci., 16 (2) (1978) 185-–225.
  * [24] P. D. Seymour and R. Thomas, Graph searching and a min-max theorem for tree-width, J. Combin. Theory Ser. B, 58 (1) (1993) 22–33.
  * [25] Z. Tuza and X. Zhu. Topics in Chromatic Graph Theory, volume 156 of Encyclopedia of Mathematics and Its Applications, chapter: Colouring games, pages 304–326. Cambridge University Press, (2015).