# Distance-balancing of cube-connected cycles graphs

Mokhtar Aouina  Western Illinois University
Macomb, Illinois, 61438<EMAIL_ADDRESS>,  Hamed Karami  Georgia State
University
Atlanta, Georgia, 30303<EMAIL_ADDRESS>and  Douglas J. LaFountain
Western Illinois University
Macomb, Illinois, 61438<EMAIL_ADDRESS>
###### Abstract.

We show that cube-connected cycles graphs $CCC_{n}$ are distance-balanced, and
nicely distance-balanced if and only if $n$ is even.

AMS 2020 Subject Classification: 05C12, 05C15

Keywords: distance-balanced; nicely distance-balanced; cube-connected cycles
graphs

##  1\. Introduction

The concept of distance-balanced graphs was implicitly introduced by Handa,
where he conjectured that a bipartite distance-balanced graph which is not a
cycle must be 3-connected [9]. However, this term itself is due to the work of
Jerebic, Klavžar and Rall, who considered distance-balanced graphs in terms of
different graph products [12]. Since then, much work has been done to find
interesting properties of these graphs [2, 14, 16], including to see if a
given family of graphs is distance-balanced or not. This line of inquiry has
previously been fruitful for generalized Petersen graphs $GP(n,k)$ and Hamming
graphs $H(n,q)$ [3, 13, 15]. For example, Jerebic, Klavžar and Rall originally
conjectured that for any $k\geq 2$ there exists an $N$ for which $GP(n,k)$ is
not a distance-balanced graph for all $n\geq N$ [12]; this conjecture was
proved by Yang, Hou, Li and Zhong [20]. In addition, Frelih generalized the
concept of distance-balanced graphs to $\ell$-distance-balanced graphs where
$\ell$ is a positive integer and a lower bound for the diameter of the graph
[5]. Using this definition, Ma, Wang and Klavžar partially solved a conjecture
of Miklavič and Sparl [18] by proving that for large $n$ compared to $k$, the
generalized Petersen graph $GP(n,k)$ is $\textrm{diam}(GP(n,k))$-distance-
balanced [17].

Our paper continues in this direction by studying a given family of graphs to
see if it is distance-balanced or not, as well as an additional property,
first introduced by Kutnar and Miklavič, of being nicely distance-balanced
[16]. Specifically, we consider the distance-balanced and nicely distanced-
balanced properties of cube-connected cycles graphs, denoted $CCC_{n}$. Cube-
connected cycles are a family of graphs introduced by Preparata and Vuillemin
for use as a network topology in parallel computing [19]. These graphs are
3-regular, connected and Cayley [1], and properties such as their diameter and
the existence of cycles of all lengths have been studied [6, 7, 11]. In this
note, we show that all cube-connected cycles graphs are distance-balanced, but
nicely distanced-balanced if and only if they are derived from a hypercube in
even dimensions. Since distance-regular graphs are nicely distance-balanced
[4, 16], this also shows that cube-connected cycles graphs are not distance-
regular when formed from hypercubes in odd dimensions.

The structure of the paper is as follows. In Section 2 we review the
definitions of our objects of interest, and also establish properties of the
automorphism group of cube-connected cycles that allow us to conclude in
Proposition 2.5 that $CCC_{n}$ is distance-balanced for all $n$. In Section 3
we then introduce a new way to represent paths in $CCC_{n}$, which is then
applied in Section 4 to prove our main Theorem 4.4 that $CCC_{n}$ is nicely
distance-balanced if and only if $n$ is even.

##  2\. Distance-balancing in $CCC_{n}$

We begin with the definitions of the objects and properties of interest. Let
$G$ be a finite graph with vertices $V$ and edges $E$. Given an edge $uv\in
E$, let $W_{u,v}=\\{x\in V\ :\ d(x,u)<d(x,v)\\}$, and similarly
$W_{v,u}=\\{x\in V\ :\ d(x,v)<d(x,u)\\}$. Also denote $W^{v}_{u}=\\{x\in V\ :\
d(x,u)=d(x,v)\\}$. Then $G$ is said to be distance-balanced if for any edge
$uv\in E$, $|W_{u,v}|=|W_{v,u}|$. $G$ is said to be nicely distance-balanced
if there exists a constant $k\in\mathbb{N}$ such that for any edge $uv\in E$,
$|W_{u,v}|=|W_{v,u}|=k$.

The hypercube graph $Q_{n}$ is the graph whose vertices and edges correspond
combinatorially to those of the unit hypercube in $\mathbb{R}^{n}$.
Notationally, the vertices of $Q_{n}$ are binary strings of length $n$, and
edges connect two vertices whose strings differ in just one digit. The
labeling of vertices of $Q_{n}$ is not unique; in particular, we have the
following initial lemma which is common knowledge, but which nevertheless will
be useful in what follows.

######  Lemma 2.1.

A choice of vertex $u$ in $Q_{n}$ as $00\cdots 0$, along with a choice of
labeling for the $n$ vertices adjacent to $u$, determines the labeling of all
vertices in $Q_{n}$.

Proof. The automorphism group Aut($Q_{n}$) has order $2^{n}n!$ (see for
example [10]), and each automorphism corresponds to a distinct labeling of the
vertices of $Q_{n}$. Specifically, there are $2^{n}$ vertices in $Q_{n}$, and
by Lemma 3.1.1 in [8] there is a subgroup $H$ of Aut$(Q_{n})$, where
$|H|=2^{n}$ and each element of $H$ is translation by a fixed binary
$n$-string; this establishes vertex-transitivity of $Q_{n}$, and allows us to
label any vertex as $00\cdots 0$. Moreover, the discussion following Lemma
3.1.1 in [8] identifies another subgroup $K$ of Aut$(Q_{n})$ which consists of
permutations of digits in all $n$-strings, so that $|K|=n!$; this corresponds
to the $n!$ permutations of the vertices $100\cdots 00,010\cdots
00,\dots,000\cdots 01$ adjacent to $00\cdots 0$. Since $H\cap K$ is just the
identity element, it follows that Aut$(Q_{n})=HK$, so that the choice of a
vertex as $00\cdots 0$ along with a choice of a labeling of its $n$
neighboring vertices determines the labeling of the entire graph. $\Box$

The cube-connected cycles graph $CCC_{n}$ is the graph where each vertex of
the hypercube graph $Q_{n}$ is replaced by an $n$-cycle. We can label vertices
in $CCC_{n}$ by adding an extra digit to the binary strings of $Q_{n}$ in
order to keep track of the $n$ vertices within each cycle. Specifically, in
$CCC_{n}$ vertices are $(n+1)$-strings of the form $x_{1}x_{2}\dots x_{n}k$,
where each $x_{i}\in\\{0,1\\}$ , $k\in\\{1,\dots,n\\}$, and two vertices are
equal if and only if each digit in their strings are equal. The $x_{i}$ are
referred to as cube digits, the $k$ as the cycle digit. Edges are of two
types: the first kind, termed a cycle edge, connects two vertices whose cube
digits are equal but whose cycle digit differs by 1 (where we consider the
cycle digits of 1 and $n$ as differing by 1, cyclically). Thus cycle edges
connect consecutive vertices in the same cycle. The second kind of edge,
termed a cube edge, connects two vertices whose cycle digits are equal to a
common value $k$, and whose cube digits only differ in the $k$-th digit
$x_{k}$. Thus cube edges connect adjacent cycles in such a way that $CCC_{n}$
is 3-regular.

Important from the outset is the observation that the labeling of $CCC_{n}$ is
also not unique. In particular, we have the following lemma.

######  Lemma 2.2.

A choice of a vertex $u$ in $CCC_{n}$ as $000\cdots 01$, along with a choice
of orientation for the cycle containing $u$, determines the labeling of all
vertices in $CCC_{n}$.

Proof. Since $CCC_{n}$ is a Cayley graph, it is vertex-transitive, so we may
label any vertex $u$ as $000\cdots 01$. Once we then choose an orientation for
the cycle containing $u$, that specifies the labeling of all other vertices in
that cycle as $000\cdots 02$ through $000\cdots 0n$. Then by the cube edge
relations, this determines the cube digits of all vertices in each neighboring
cycle; specifically, the vertices in the cycle connected by a cube edge to
$000\cdots 0k$ will have a 1 in the $k$-th cube digit and $0$’s in the other
cube digits. As a result, by Lemma 2.1, this in fact determines the cube
digits for all cycles, hence cube digits for all vertices in $CCC_{n}$.
Finally, given any vertex in $CCC_{n}$, it is then connected by a cube edge to
another vertex, and they differ in some $k$-th cube digit, thus determining
their cycle digit to be $k$; hence all labels for all vertices in $CCC_{n}$
are then fixed. $\Box$

We then have two propositions which follow from Lemma 2.2.

######  Proposition 2.3.

$|Aut(CCC_{n})|=n2^{n+1}$.

Proof. The automorphisms of $CCC_{n}$ are in one-to-one correspondence with
distinct vertex labelings of $CCC_{n}$. Since there are $n2^{n}$ vertices in
$CCC_{n}$, there are $n2^{n}$ choices for the vertex $000\cdots 01$, and then
there are 2 choices of orientation for the cycle containing that vertex. Hence
by Lemma 2.2 there are $n2^{n+1}$ different vertex labelings of $CCC_{n}$ and
the proposition follows. $\Box$

######  Proposition 2.4.

Given an edge $uv$ in $CCC_{n}$, there is an automorphism $\varphi\in
Aut(CCC_{n})$ such that $\varphi(u)=v$ and $\varphi(v)=u$.

Proof. If $uv$ is a cube edge, then by Lemma 2.2 there is a labeling of
$CCC_{n}$ (actually two) which labels $u=000\cdots 01$ and $v=100\cdots 01$;
but there is also a labeling of $CCC_{n}$ which reverses this, labeling
$u=100\cdots 01$ and $v=000\cdots 01$. Thus there is an automorphism $\varphi$
which matches up vertices with the same digits under these two labelings, so
that $\varphi(u)=v$ and $\varphi(v)=u$.

On the other hand, if $uv$ is a cycle edge, then by Lemma 2.2 there is a
labeling of $CCC_{n}$ which labels $u=000\cdots 01$ and $v=000\cdots 0n$; but
there is also a labeling of $CCC_{n}$ which reverses this, labeling
$u=000\cdots 0n$ and $v=000\cdots 01$. Thus again there is an automorphism
$\varphi$ which matches up vertices with the same digits under these two
labelings, so that $\varphi(u)=v$ and $\varphi(v)=u$. $\Box$

We now have our first major result.

######  Proposition 2.5.

$CCC_{n}$ is distance-balanced for all $n$.

Proof. By Proposition 2.4 in [12], if $G$ is a graph such that for any edge
$uv$ in $G$, there is an automorphism $\varphi\in Aut(G)$ that results in
$\varphi(u)=v$ and $\varphi(v)=u$, then $G$ is distance-balanced. By
Proposition 2.4 above, $CCC_{n}$ is such a graph, and hence $CCC_{n}$ is
distance-balanced. $\Box$

To investigate the nice distance-balancing of $CCC_{n}$, we need a new method
of understanding minimum paths and distance, which we now introduce in the
next section.

##  3\. Interval-with-ends diagrams for paths in $CCC_{n}$

A path in $CCC_{n}$ between two vertices is a sequence of cube and cycle
edges. Whenever an edge is traversed, exactly one digit changes in the
corresponding vertex string; if it is a cycle edge, the cycle digit will
change by 1, either increasing or decreasing (in the cyclic ordering of
$1,\dots,n$); and if it is a cube edge, a cube digit will change from a 1 to
0, or vice versa. More specifically, if we are at a vertex $x_{1}x_{2}\cdots
x_{n}k$, we only have three directions we can go, namely we can either change
the cycle digit $k$ to $k-1$ or $k+1$ (in the cyclic ordering of $1,\dots,n$),
and traverse a cycle edge; or we can change the $k$-th cube digit $x_{k}$ and
traverse that cube edge. With this in mind, our first goal in this section is
to establish a new way to represent paths in $CCC_{n}$.

By vertex-transitivity, we may focus on paths from $u=00\cdots 01$ to another
vertex $x=x_{1}x_{2}\dots x_{n}k$. We begin with an informal discussion of a
path from $u$ to $x$ before formalizing our observations. In order to move
from $u=00\cdots 01$ to $x=x_{1}x_{2}\cdots x_{n}k$ via a path $\gamma$, we
need to examine which cube digits in $x$ are 1’s, for these will need to be
changed. For example, if $x_{i}=1$, then we know that $\gamma$ will need to
traverse cycle edges within some cycle until the cycle digit changes to $i$;
then the changing of the $i$-th cube digit from 0 to 1 will result in the
traversal of a cube edge, with the result that $x_{i}=1$. We then have to do
this for all such cube digits in $x$ which are $1$, and then finally move
within the last cycle until the cycle digit changes to $k$.

As a result, we can represent paths $\gamma$ in $CCC_{n}$ symbolically using
what we call an interval-with-ends (IWE) diagram, with four examples shown in
Figure 1 for IWE diagrams from $00000001$ to $01011006$ in $CCC_{7}$. To
construct an IWE diagram from $u=00\cdots 01$ to $x=x_{1}x_{2}\cdots x_{n}k$,
we do the following:

  1. (1)

Form a loop connecting the numbers $1$ through $n$; these represent the cycle
digits for vertices in the path.

  2. (2)

Circle all of the numbers $i$ where the $i$-th cube digit needs to be changed
from $0$ to $1$ in moving from $u$ to $x$.

  3. (3)

Choose an interval along the loop that includes all the circled digits, has
endpoints at circled digits, and has angular support less than $2\pi$; if
there are $m$ circled digits, we have $m$ possible intervals.

  4. (4)

Since we begin at $u$ with cycle digit 1, draw an arrow from $1$ to one of the
endpoints of the interval, along the loop, with angular support less than
$2\pi$. We call this arrow the initial end; there are four possibilities for
it, depending on which endpoint of the interval it connects to, and if it
proceeds clockwise or counterclockwise.

  5. (5)

Since we end at $x$ with cycle digit $k$, draw an arrow from the other
endpoint of the interval to $k$, along the loop, with angular support less
than $2\pi$. We call this arrow the terminal end; once the initial end is
fixed, there are two possibilities for the terminal end, depending if it
proceeds clockwise or counterclockwise.

We note that the interval may be an empty interval in the case where both $u$
and $x$ are in the same cycle in $CCC_{n}$, in which case we then have a
single end connecting 1 to $k$ as our IWE diagram.

2pt $7$ at 124 448 $6$ at 67 269 $5$ at 173 106 $4$ at 372 94 $3$ at 513 254
$2$ at 460 420 $1$ at 300 515 interval at 30 500 initial end at 440 540
terminal end at 20 110 (c) at 300 -10

$7$ at 120 1094 $6$ at 67 914 $5$ at 170 746 $4$ at 370 736 $3$ at 510 897 $2$
at 460 1067 $1$ at 296 1160 interval at 570 820 initial end at 440 1190
terminal end at 10 760 (a) at 300 655

$7$ at 978 1090 $6$ at 920 914 $5$ at 1027 747 $4$ at 1225 734 $3$ at 1367 895
$2$ at 1314 1067 $1$ at 1150 1160 interval at 1430 820 terminal end at 1250
970 initial end at 880 1100 (b) at 1160 655

$7$ at 980 447 $6$ at 921 270 $5$ at 1027 100 $4$ at 1227 90 $3$ at 1364 250
$2$ at 1316 420 $1$ at 1152 515 interval at 890 500 initial end at 890 100
terminal end at 1250 320 (d) at 1160 -10

Figure 1. Four examples of interval-with-ends (IWE) diagrams from $00000001$
to $01011006$ in $CCC_{7}$. Part (a) has length 8, since three circles are
included in the interval, and five edges in the loop are included in the
interval-with-ends; part (b) has length 13; part (c) has length 11; and part
(d) has length 16.

There are multiple possible IWE diagrams from $u$ to $x$; yet for a given IWE
diagram, there is a shortest path $\gamma$ in $CCC_{n}$ from $u$ to $x$
supported by that IWE diagram, namely the following: First, we proceed
monotonically along the initial end from $1$ to the first endpoint of the
interval, and each edge we traverse in the initial end corresponds to a cycle
edge in $\gamma$. Then, at the endpoint of the interval, we have a circled
digit, and that circle corresponds to traversing a cube edge in $\gamma$. We
then proceed monotonically along the interval, and every circle we encounter
represents a cube edge in $\gamma$, with every edge in the interval a cycle
edge in $\gamma$, until we reach the end of the interval with our final circle
and cube edge. Then, we proceed monotonically along the terminal end to $k$,
and every edge in the terminal end corresponds to a cycle edge in $\gamma$.
Thus given an IWE diagram $D$, we will denote its length by $|D|$, with

$\displaystyle|D|$ $\displaystyle=$ $\displaystyle\textrm{(\\# of edges in
initial end)}+\textrm{(\\# of edges in terminal end)}$
$\displaystyle+\textrm{\ (\\# of edges in interval)}+\textrm{(\\# of circled
digits)}$

As indicated in Figure 1, the length of $\gamma$ for the IWE diagram in part
(a) is 8, for part (b) is 13, for part (c) is 11, and for part (d) is 16. Note
that if we do not move monotonically along the ends of the interval, but
double back, or change cube digits other than the circled ones, this can give
us other paths in $CCC_{n}$. But these will necessarily be longer than $|D|$.
Furthermore, any path in $CCC_{n}$ between $u=00\cdots 01$ and
$x=x_{1}x_{2}\cdots x_{n}k$ can be mapped out in this cycle digit loop, where
we record the edges traversed in the cycle digit loop, and circle the cube
digits changed; although this mapping may not be an IWE itself, nevertheless
an IWE diagram $D$ will be a subset of it, and hence the length of that path
will be at least $|D|$. Therefore, if $u=00\cdots 01$ and $x=x_{1}x_{2}\cdots
x_{n}k$, we have that in $CCC_{n}$,

$d(u,x)=\min\\{|D|:D\textrm{\ is an IWE diagram from\ }u\textrm{\ to\ }x\\}.$

Thus $d(u,x)=|D|$ for at least one IWE diagram $D$, which gives a shortest
path $\gamma$ in $CCC_{n}$ from $u$ to $x$.

##  4\. Nice distance-balancing in $CCC_{n}$

In order to determine under what conditions $CCC_{n}$ may be nicely distance-
balanced, we first consider cube edges. We recall that in $CCC_{n}$ there are
a total of $n2^{n}$ vertices.

######  Proposition 4.1.

If $uv$ is a cube edge in $CCC_{n}$, then $|W_{u,v}|=|W_{v,u}|=n2^{n-1}$.

Proof. We may assume that $u=00\cdots 01$ and $v=10\cdots 01$. We claim that
any vertex with a 0 as its first cube digit is in $W_{u,v}$, and any vertex
with a 1 as its first cube digit is in $W_{v,u}$. To see that $x=1x_{2}\cdots
x_{n}k\in W_{v,u}$, consider an IWE diagram $D$ from $u$ to $x$ such that
$|D|=d(u,x)$. Then observe that since $u$ and $v$ differ only in the first
cube digit, an IWE diagram $D^{\prime}$ from $v$ to $x$ can be obtained by
using $D$, but deleting the circle around 1. Thus $d(x,v)\leq
d(u,x)-1<d(u,x)$, so that $x\in W_{v,u}$. An entirely similar argument shows
that if $x=0x_{2}\cdots x_{n}k$, then $x\in W_{u,v}$, and this proves the
proposition. $\Box$

######  Remark 4.2.

Since $|W_{u,v}|=|W_{v,u}|=n2^{n-1}$ we also have that $W^{v}_{u}=\emptyset$.

We now turn to cycle edges for the following proposition.

######  Proposition 4.3.

If $uv$ is a cycle edge in $CCC_{n}$, then $W^{v}_{u}=\emptyset$ if and only
if $n$ is even.

Proof. We may assume throughout the proof that $u=00\cdots 01$ and $v=00\cdots
0n$.

When $n$ is odd, consider the vertex $x=00\cdots 0\left(\frac{n+1}{2}\right)$.
It is in the same cycle as both $u$ and $v$, and so the IWE diagram $D_{u}$
that realizes $d(x,u)$ is a single end that connects $1$ to
$\left(\frac{n+1}{2}\right)$, with length $\frac{n-1}{2}$. Similarly, the IWE
diagram $D_{v}$ that realizes $d(x,v)$ is a single end that connects $n$ to
$\left(\frac{n+1}{2}\right)$, with length $\frac{n-1}{2}$. Thus
$d(x,u)=d(x,v)$ in $CCC_{n}$, with $x\in W_{u}^{v}$. We therefore conclude
that $W^{v}_{u}\neq\emptyset$ when $n$ is odd.

In general, we now consider an arbitrary $x\in W^{v}_{u}$ in $CCC_{n}$, and we
will show that $n$ must be odd; this will conclude the proof. To set notation,
we assume that $x=x_{1}x_{2}\cdots x_{n}k$. We first consider the case where
$x_{i}=0$ for all $i\in\\{1,\dots,n\\}$, so that $x$ lies in the same cycle as
both $u$ and $v$. Then the IWE diagrams realizing $d(x,u)$ and $d(x,v)$ are
just single ends connecting $u$ to $x$ and $v$ to $x$, respectively. Since
$x\in W^{v}_{u}$ with $d(x,u)=d(x,v)$, we must have $d(x,u)=k-1=d(x,v)=n-k$,
so that $n+1=2k$; thus $n$ must be odd.

We now consider the case where $x$ does not lie in the same cycle as $u$ and
$v$, and we observe that the cube digits that need to be changed to 1 in
moving from $u$ to $x$ are the same cube digits that need to be changed in
moving from $v$ to $x$. We fix an IWE diagram $D$ realizing $d(x,u)$, and
observe that its interval $I$ will have endpoints at numbers $i$ and $j$ which
represent cube digits that need to be changed. An example is shown in Figure
2, where the specific cyclic ordering of $i,j,k$ will not enter into the
argument. Likewise we only assume that of $1,i,j,k$ and $n$, only $1$ and $n$
are necessarily distinct.

2pt

$i$ at 468 400 $n$ at 200 500 $1$ at 350 500 $I$ at 20 300

$k$ at 150 120 $j$ at 370 90

Figure 2. An interval $I$ for a possible IWE diagram realizing $d(x,u)$.

Our first observation is that no end emanating from $1$ to either $i$ or $j$
can proceed counterclockwise, for if it did, this IWE diagram could work for
$v$, but with one less edge, hence resulting in $d(x,v)<d(x,u)$; but this is
not true, since we are assuming $x\in W^{v}_{u}$. So any end emanating from
$1$ for an IWE diagram realizing $d(x,u)$ must proceed clockwise. Likewise,
any end emanating from $n$ for an IWE diagram realizing $d(x,v)$ must proceed
counterclockwise.

We now consider the case where the IWE diagram $D_{u}$ realizing $d(x,u)$ has
the same interval as the IWE diagram $D_{v}$ realizing $d(x,v)$. In this case,
denote the number of edges in the initial and terminal ends for $D_{u}$, with
an endpoint at $1$ and $k$ respectively, as $\alpha_{u}^{1}$ and
$\alpha_{u}^{k}$. Likewise denote the number of edges in the initial and
terminal ends for $D_{v}$, with an endpoint at $n$ and $k$ respectively, as
$\beta_{v}^{n}$ and $\beta_{v}^{k}$. Since $D_{u}$ and $D_{v}$ share the same
interval with the same circled cube digits, and we are assuming
$d(x,u)=d(x,v)$, we must have

(1) $\alpha_{u}^{1}+\alpha_{u}^{k}=\beta_{v}^{n}+\beta_{v}^{k}.$

Observe that each of these quantities has limited possibilities. Specifically,
from the reasoning in the preceding paragraph, $\alpha_{u}^{1}$ must be either
$i-1$ or $j-1$, and likewise $\beta_{v}^{n}$ must be $n-i$ or $n-j$. The
possibilities for $\alpha_{u}^{k}$ and $\beta_{v}^{k}$ are more numerous, and
so we take a moment to focus on $\alpha_{u}^{k}$ and observe that the terminal
end with endpoint at $k$ has four options:

  * $\bullet$

if it joins $k$ to $i$ without passing through $n$, then
$\alpha_{u}^{k}=|k-i|$ and $\alpha_{u}^{1}=j-1$;

  * $\bullet$

if it joins $k$ to $i$ and passes through $n$, then $\alpha_{u}^{k}=n-k+i$ and
$\alpha_{u}^{1}=j-1$;

  * $\bullet$

if it joins $k$ to $j$ without passing through $n$, then
$\alpha_{u}^{k}=|k-j|$ and $\alpha_{u}^{1}=i-1$;

  * $\bullet$

if it joins $k$ to $j$ and passes through $n$, then $\alpha_{u}^{k}=n-k+j$ and
$\alpha_{u}^{1}=i-1$.

Likewise considering $\beta_{v}^{k}$, the options for its terminal end with
endpoint at $k$ will be:

  * $\bullet$

if it joins $k$ to $i$ without passing through $n$, then $\beta_{u}^{k}=|k-i|$
and $\beta_{u}^{n}=n-j$;

  * $\bullet$

if it joins $k$ to $i$ and passes through $n$, then $\beta_{u}^{k}=n-k+i$ and
$\beta_{u}^{n}=n-j$;

  * $\bullet$

if it joins $k$ to $j$ without passing through $n$, then $\beta_{u}^{k}=|k-j|$
and $\beta_{u}^{n}=n-i$;

  * $\bullet$

if it joins $k$ to $j$ and passes through $n$, then $\beta_{u}^{k}=n-k+j$ and
$\beta_{u}^{n}=n-i$.

The key observation is that regardless of which possibility occurs, the left
hand side of Equation 1 will contain a $-1$ term, along with a $\pm i$, $\pm
j$, and $\pm k$ term, and possibly one $n$ term; likewise the right hand side
of Equation 1 will contain $n$, along with a $\pm i$, $\pm j$, and $\pm k$
term, and possibly one more $n$ term. The result is that when we isolate the
$n$’s and 1 on the right hand side, we obtain an even left hand side with two
terms each of $i,j$ and $k$. Therefore, in order for $n$ to have an integer
solution, $n$ must be odd.

We conclude by considering the case where the IWE diagram $D_{u}$ realizing
$d(x,u)$ does not use the same interval as the IWE diagram $D_{v}$ realizing
$d(x,v)$. This case does not apply when there is just one circled cube digit
that needs to be changed, and so from here on we may assume that $i\neq j$.
For this case denote the endpoints of the interval for $D_{v}$ as $i^{\prime}$
and $j^{\prime}$, and the interval itself as $I^{\prime}$, where we likewise
necessarily have $i^{\prime}\neq j^{\prime}$. An example is shown in Figure 3,
where the two intervals are colored in light gray and dark gray, respectively.

2pt

$i^{\prime}$ at 100 390

$i$ at 470 400 $n$ at 200 500 $1$ at 350 500 $k$ at 490 205

$j^{\prime}$ at 145 120 $j$ at 370 90

$I$ at 20 250 $I^{\prime}$ at 570 250

Figure 3. Intervals $I$ and $I^{\prime}$ for possible IWE diagrams realizing
$d(x,u)$ and $d(x,v)$, respectively.

We now observe that the total number of edges in $I$ will be $n-|i-j|$, and
the total number of edges in $I^{\prime}$ will be $n-|i^{\prime}-j^{\prime}|$.
As above, denote the number of edges in the initial and terminal ends for
$D_{u}$ as $\alpha_{u}^{1}$ and $\alpha_{u}^{k}$, respectively. Likewise
denote the number of edges in the initial and terminal ends for $D_{v}$ as
$\beta_{v}^{n}$ and $\beta_{v}^{k}$, respectively. Since $D_{u}$ and $D_{v}$
share the same circled cube digits, and we are assuming $d(x,u)=d(x,v)$, we
must have

$n-|i-j|+\alpha_{u}^{1}+\alpha_{u}^{k}=n-|i^{\prime}-j^{\prime}|+\beta_{v}^{n}+\beta_{v}^{k}$

or

(2)
$-|i-j|+\alpha_{u}^{1}+\alpha_{u}^{k}=-|i^{\prime}-j^{\prime}|+\beta_{v}^{n}+\beta_{v}^{k}.$

As above, the $\alpha_{u}^{1}+\alpha_{u}^{k}$ terms will contain a $-1$ term,
along with a $\pm i$, $\pm j$, and $\pm k$ term, and possibly one $n$ term;
similarly, the $\beta_{v}^{n}+\beta_{v}^{k}$ terms will contain $n$, along
with a $\pm i^{\prime}$, $\pm j^{\prime}$, and $\pm k$ term, and possibly one
more $n$ term. As a result, now the left hand side of Equation 2 has two terms
each of $i$ and $j$, and one term of $k$, and the right hand side has two
terms each of $i^{\prime}$ and $j^{\prime}$, and one term of $k$. Moving all
these terms to the left hand side, and all $n$’s and the 1 to the right hand
side, we see the left hand side is even with two terms each of
$i,i^{\prime},j,j^{\prime}$ and $k$. Thus, again in order for $n$ to have an
integer solution, $n$ must be odd. $\Box$

Our main theorem then follows.

######  Theorem 4.4.

$CCC_{n}$ is nicely distance-balanced if and only if $n$ is even.

Proof. We know by Proposition 4.1 that if $uv$ is a cube edge,
$|W_{u,v}|=|W_{v,u}|=n2^{n-1}$, and by Remark 4.2 we know
$W_{u}^{v}=\emptyset$. But if $uv$ is a cycle edge and $n$ is odd, by
Proposition 4.3 we know that $W^{v}_{u}\neq\emptyset$. Applying now
Proposition 2.5, we must have $|W_{u,v}|=|W_{v,u}|<n2^{n-1}$. Hence for $n$
odd, $CCC_{n}$ is not nicely distance-balanced.

On the other hand, if $n$ is even and $uv$ is a cycle edge, then by
Proposition 4.3 we know that $W^{v}_{u}=\emptyset$, so by Proposition 2.5 we
must have $|W_{u,v}|=|W_{v,u}|=n2^{n-1}$. Hence for $n$ even, $CCC_{n}$ is
nicely distance-balanced. $\Box$

######  Remark 4.5.

As distance-regular graphs are nicely distance-balanced, Theorem 4.4 proves
that the graphs $CCC_{n}$, where $n$ is odd, cannot be distance-regular (see
[4] for a definition and background on distance-regular graphs).

## References

  * [1] S.B. Akers, B. Krishnamurthy, A group-theoretic model for symmetric interconnection networks, IEEE Trans. Comp. 38 (4) (1989) 555-566.
  * [2] K. Balakrishnan, M. Changat, I. Peterin, S. Spacapan, P. Sparl, A.R. Subhamathi, Strongly distance-balanced graphs and graph products, Eur. J. Comb. 30 (2009) 1048-1053.
  * [3] M. Behzad, P. Hatami, E.S. Mahmoodian, Minimum vertex covers in the generalized Petersen graphs $P(n,2)$, Bull. Inst. Combin. Appl. 56 (2009), 98-102.
  * [4] A.E. Brouwer, W.H. Haemers, Distance-regular graphs, Springer (2012).
  * [5] B. Frelih, Različni vidiki povezave regularnosti v grafih, Ph.D. dissertation (2014) .
  * [6] I. Fris, I. Havel, P. Liebl, The diameter of the cube-connected cycles, Inform. Process. Lett. 61 (3) (1997), 157-160.
  * [7] A. Germa, M.C. Heydemann, D. Sotteau, Cycles in the cube-connected cycles graph, Discrete Appl. Math. 83 (1998), 135-155.
  * [8] C. Godsil, G. Royle, Algebraic Graph Theory, Springer (2001).
  * [9] K. Handa, Bipartite graphs with balanced $(a,b)$-partitions, Ars Combin. 51 (1999), 113-119.
  * [10] F. Harary, The automorphism group of a hypercube, J. Univers. Comput. Sci. 6 (1) (2000), 136-138.
  * [11] L.H. Hsu, T.Y. Ho, Y.H. Ho, C.W. Tsay, Cycles in cube-connected cycles graphs, Discrete Appl. Math. 167 (2014), 163-171.
  * [12] J. Jerebic, S. Klavžar, D.F. Rall, Distance-balanced graphs, Ann. Comb. 12 (2008), 71-79.
  * [13] H. Karami, Edge distance-balanced of Hamming graphs, J. Discrete Math. Sci. Cryptogr. 25 (8) (2022), 2667-2672.
  * [14] K. Kutnar, A. Malnič, D. Marusič, Š. Miklavič, Distance-balanced graphs: Symmetry conditions, Discrete Math. 306 (2006) 1881-1894.
  * [15] K. Kutnar, A. Malnič, D. Marusič, Š. Miklavič, The strongly distance-balanced property of the generalized Petersen graphs, Ars Math. Cont. 2 (2009) 41-47.
  * [16] K. Kutnar, Š. Miklavič, Nicely distance-balanced graphs, Eur. J. Comb. 39 (2014) 57-67.
  * [17] G. Ma, J. Wang, S. Klavžar, On distance-balanced generalized Peterson graphs, Ann. Comb. (2023).
  * [18] Š. Miklavič, P. Sparl, $\ell$-distance-balanced graphs, Discrete Appl. Math 244 (2018), 143-154.
  * [19] F.P. Preparata, J. Vuillemin, The cube-connected cycles: a versatile network for parallel computation, Commun. ACM 25 (5) (1981), 300-309.
  * [20] R. Yang, X. Hou, N. Li, W. Zhong, A note on the distance-balanced property of generalized Peterson graphs, Electron. J. Combin. 16 (1) (2009), 1-3.