# Symmetry Parameters of Praeger-Xu Graphs

Sally Cockburn  Max Klivans This research was supported by The Monica Odening
’05 Student Internship and Research Fund in Mathematics.

###### Abstract

Praeger-Xu graphs are connected, symmetric, 4-regular graphs that are unusual
both in that their automorphism groups are large, and in that vertex
stabilizer subgroups are also large. Determining number and distinguishing
number are parameters that measure the symmetry of a graph by investigating
additional conditions that can be imposed on a graph to eliminate its
nontrivial automorphisms. In this paper, we compute the values of these
parameters for Praeger-Xu graphs. Most Praeger-Xu graphs are
2-distinguishable; for these graphs we also proved the cost of
2-distinguishing.

Keywords: Praeger-Xu graphs; determining number; distinguishing number; cost
of 2-distinguishing.

Subject Classification: 05C15, 05C25, 05C69

##  1 Introduction

A finite simple graph $G=(V,E)$ consists of a finite, nonempty set $V$ of
vertices, and a set of $2$-subsets of $V$, called edges. An appealing feature
of graphs is that they can be represented geometrically, with dots
corresponding to vertices and lines between dots corresponding to edges.
Certain graphs have the property that when the positions of the dots are
carefully chosen, this geometric representation displays visual symmetry.
However, a graph is an set-theoretic object, not a drawing. There are various
ways to give a rigorous mathematical characterization of symmetry.

An automorphism $\alpha$ of a graph $G=(V,E)$ is a permutation of $V$ such
that for all $u,v\in V$, $\\{u,v\\}\in E$ if and only if
$\\{\alpha(u),\alpha(v)\\}\in E$. The set of automorphisms of $G$, denoted
$\operatorname{Aut}(G)$, is a group under composition. For example, the
automorphism group of the complete graph on $n$ vertices is the entire group
of permutations on $n$ elements; that is, $\operatorname{Aut}(K_{n})=S_{n}$.
For $n\geq 3$, the automorphism group of the cycle $C_{n}$ is the dihedral
group $D_{n}$, consisting of rotations and reflections.

One way of characterizing the symmetry of a graph is to determine whether the
vertices and/or edges play the same role, in the following sense. A graph $G$
is vertex-transitive if for all $u,v\in V$, there is
$\alpha\in\operatorname{Aut}(G)$ such that $\alpha(v)=u$. Similarly, $G$ is
edge-transitive if for all $\\{u,v\\},\\{x,y\\}\in E$, there is
$\alpha\in\operatorname{Aut}(G)$ such that
$\alpha(\\{u,v\\})=\\{\alpha(u),\alpha(v)\\}=\\{x,y\\}$. More stringently, a
graph is arc-transitive if for all $\\{u,v\\},\\{x,y\\}\in E$, there is
$\alpha\in\operatorname{Aut}(G)$ such that $\alpha(u)=x$ and $\alpha(v)=y$.
Connected, arc-transitive graphs are automatically both vertex-transitive and
edge-transitive, and are simply called symmetric graphs. Complete graphs
$K_{n}$ and cycles $C_{n}$ are examples of symmetric graphs.

Another way of characterizing the symmetry of a graph $G$ is to quantify extra
measures that can taken to prevent the existence of nontrivial automorphisms
of $G$. As one example, we could require that automorphisms of $G$ fix point-
wise a subset $S$ of vertices. If the only automorphism doing so is the
identity, then $S$ is called a determining set of $G$. The determining number
of $G$, denoted $\operatorname{Det}(G)$, is the minimum size of a determining
set of $G$. (Some authors use the term fixing instead of determining, for both
sets and numbers.) Graphs with no nontrivial automorphisms, sometimes called
asymmetric or rigid graphs, have determining number $0$; at the opposite end
of the spectrum, $\operatorname{Det}(K_{n})=n-1$. A minimum determining set
for $C_{n}$ is any set of two non-antipodal vertices, so
$\operatorname{Det}(C_{n})=2$.

As another example, we could paint the vertices with different colors and
require that automorphisms preserve set-wise the color classes. Graph $G$ is
d-distinguishable if the vertices can be colored with $d$ colors in such a way
that the only automorphism preserving the color classes is the identity. The
distinguishing number of $G$, denoted $\operatorname{Dist}(G)$, is the minimum
number of colors required for a distinguishing coloring. For a discussion of
elementary properties of determining numbers and distinguishing numbers, as
well as the connections between them, see [2].

Remarkably, many infinite families of symmetric graphs have been found to have
distinguishing number $2$, including hypercubes [3], Cartesian powers $G^{\Box
n}$ of a connected graph where $G\neq K_{2},K_{3}$ and $n\geq 2$ [1, 10, 12]
and Kneser graphs $K_{n:k}$ with $n\geq 6,k\geq 2$ [2]. Boutin [5] introduced
an additional invariant in such cases; the cost of 2-distinguishing $G$,
denoted $\rho(G)$, is the minimum size of a color class in a 2-distinguishing
coloring of $G$.

In this paper, we find these symmetry parameters for a family of symmetric
graphs called Praeger-Xu graphs. They are remarkable among all connected,
symmetric, 4-regular graphs for having very large automorphism groups.
Moroever, there is an infinite family of Praeger-Xu graphs with the property
that the smallest subgroup of automorphisms that acts transitively on the
vertices has an arbitrarily large vertex stabilizer. For these and more
results on Praeger-Xu graphs, see [15], [13] and [11]. The large automorphism
group suggest that they might have large determining and distinguishing
numbers; the large vertex stabilizers suggest the opposite.

This paper is organized as follows. In Section 2, we provide a definition of
the Praeger-Xu graphs and facts about their automorphism groups. In Section 3,
we show that most Praeger-Xu graphs are twin-free; for those with twins, we
use a quotient graph construction to find the determining and distinguishing
number. In Section 4, we find the determining number for twin-free Praeger-Xu
graphs. As a tool for computing distinguishing number, in Section 5 we
characterize pairs of vertices in twin-free Praeger-Xu graphs that are
interchangeable via an automorphism. Finally, in Section 6 we show that all
twin-free Praeger-Xu graphs are $2$-distinguishable and compute the cost of
$2$-distinguishing. Our results are summarized in Table 1.

Parameter | Value | Condition(s)
---|---|---
$\operatorname{Det}(\operatorname{PX}(n,k))$ | 6 | $(n,k)=(4,1)$
| $\lceil\frac{n}{k}\rceil$ |  $k\neq\frac{n}{2}$ but $(n,k)\neq(4,1)$
| $\lceil\frac{n}{k}\rceil+1=3$ | $k=\frac{n}{2}$
$\operatorname{Dist}(\operatorname{PX}(n,k))$ | 5 | $(n,k)=(4,1)$
| $3$ |  $n\neq 4$, $k=1$
| $2$ | $k\geq 2$
$\rho(\operatorname{PX}(n,k))$ | $5$ | $(n,k)=(4,2)$
$(k\geq 2)$ | $\lceil\frac{n}{k}\rceil$ |  $5\leq n<2k$, or
|  | $2k<n\text{ and }n\notin\\{0\bmod k,-1\bmod k\\}$
| $\lceil\frac{n}{k}\rceil+1$ | otherwise
Table 1: Summary of Symmetry Parameters ($n\geq 3$)

##  2 Praeger-Xu Graphs, $\operatorname{PX}(n,k)$

In 1989, Praeger and Xu [14] introduced a family of connected graphs they
denoted by $C(m,r,s)$, where $m\geq 2$, $r\geq 3$ and $s\geq 1$, that are
vertex-transitive for $r\geq s$ and arc-transitive, hence symmetric, for
$r\geq s+1$. This was part of an investigation into connected, symmetric
graphs whose automorphism groups have the property that for any vertex $v$,
the subgroup of automorphisms fixing $v$ (the stabilizer of $v$) does not act
primitively on the set of neighbors of $v$. The Praeger-Xu graphs are those
where $p=2$; the notation $PX(n,k)$ denotes $C(2,n,k)$. There are several ways
of describing Praeger-Xu graphs (see [9]); we use what is called the bitstring
model.

######  Definition 1.

Let $n\geq 3$ and $1\leq k<n$. The corresponding the Praeger-Xu graph is
$\operatorname{PX}(n,k)=(V,E)$, where $V$ is the set of all ordered pairs
$(i,x)$, where $i\in\mathbb{Z}_{n}$ and $x=x_{0}x_{1}\cdots x_{k-1}$ is a
bitstring of length $k$, and $\\{(i,x),(j,y)\\}\in E$ if and only if $j=i+1$
and $x=az_{1}z_{2}\cdots z_{k-1}$ and $y=z_{1}z_{2}\cdots z_{k-1}b$ for some
$z_{1},\dots,z_{k-1},a,b\in\mathbb{Z}_{2}$.

Throughout this paper, subscripts on bits will be considered elements of
$\mathbb{Z}_{k}$. We say that the bit $x_{j}$ in $x$ is flipped if it is
switched to $x_{j}+1$ in $\mathbb{Z}_{2}$.

There is a natural partition of $V$ into _fibres_
$\mathcal{F}_{i}=\\{(i,x):x\in\mathbb{Z}_{2}^{k}\\}$ for each
$i\in\mathbb{Z}_{n}$. Each fibre is an independent set of $2^{k}$ vertices;
every vertex in $\mathcal{F}_{i}$ is adjacent to exactly two vertices in each
of $\mathcal{F}_{i+1}$ and $\mathcal{F}_{i-1}$, so $\operatorname{PX}(n,k)$ is
$4$-regular, or tetravalent. Two fibres $\mathcal{F}_{i}$ and
$\mathcal{F}_{j}$ are antipodal if and only if $n$ is even and
$i-j=\frac{n}{2}\bmod n$.

Two Praeger-Xu graphs are illustrated in Figure 2. Figure 1(a) shows the
smallest Praeger-Xu graph having $k>1$, namely $\operatorname{PX}(3,2)$, of
order $3\cdot 2^{2}=12$. Figure 1(b) shows the larger Praeger-Xu graph
$\operatorname{PX}(20,5)$ of order $20\cdot 2^{5}=640$. In all our diagrams of
Praeger-Xu graphs, $\mathcal{F}_{0}$ is the fibre in the $12$ o’clock
position, with remaining fibres labeled consecutively clockwise. The vertices
in $\mathcal{F}_{0}$ on $\operatorname{PX}(3,2)$ have been labeled with their
bitstring components; the bitstring components of vertices in
$\mathcal{F}_{1}$ and $\mathcal{F}_{2}$ follow the same pattern. More
generally, the bitstring components are the binary representations of the
integers $0$ to $2^{k}$, starting with the innermost vertex. Throughout this
paper, we will be assuming that $n\geq 3$ and $1\leq k<n$, unless otherwise
explicitly indicated.

(a) $\operatorname{PX}(3,2)$.

(b) $\operatorname{PX}(20,5)$.

Figure 1: Two Praeger-Xu graphs.

###  2.1 Automorphisms of $\operatorname{PX}(n,k)$

In [14], Praeger and Xu described the automorphism groups of all graphs in the
family $C(p,r,s)$. We will adopt the notation used in [15] for automorphisms
of the Praeger-Xu graphs, $PX(n,k)$. The automorphism group is generated by
three different types of automorphisms.

The first is the rotation $\rho$, defined by $\rho\cdot(i,x)=(i+1,x).$
Composing $\rho$ with itself $s$ times corresponds to a rotation by $s$
fibres: $\rho^{s}\cdot(i,x)=(i+s,x)$. If $s$ is a multiple of $n$, then the
resulting map is the identity, and so we can interpret $s$ as an element of
$\mathbb{Z}_{n}$.

The second automorphism is the reflection defined by
$\mu\cdot(i,x)=(-i,x^{-}),$ where $x^{-}=(x_{0}x_{1}\cdots
x_{k-1})^{-}=x_{k-1}\cdots x_{1}x_{0}$. It is easily verified that $\mu^{2}=$
id and $\mu\rho\mu=\rho^{-1}$, so the subgroup $\langle\rho,\mu\rangle$ of
$\operatorname{Aut}(\operatorname{PX}(n,k))$ is the dihedral group $D_{n}$.

Following [15], for each $s\in\mathbb{Z}_{n}$ we let
$\mu_{s}=\rho^{s+1-k}\mu\in\langle\rho,\mu\rangle$, so that
$\mu_{s}\cdot(i,x)=(s+1-k-i,x^{-}).$ With this notation, $\mu=\mu_{k-1}$; in
particular, note that $\rho^{0}=\text{id}$ but $\mu_{0}\neq\text{id}$. We
collect some elementary facts about the reflections $\mu_{s}$ in the following
lemma.

######  Lemma 1.

Let $s,i,j\in\mathbb{Z}_{n}$.

  1. (1)

The reflection $\mu_{s}$ interchanges fibres $\mathcal{F}_{i}$ and
$\mathcal{F}_{s+1-k-i}$; equivalently, fibres $\mathcal{F}_{i}$ and
$\mathcal{F}_{j}$ are interchanged by $\mu_{i+j+k-1}$.

  2. (2)

If $n$ is odd, then each $\mu_{s}$ preserves exactly one fibre. If $n$ is even
and $s=k\bmod 2$, then $\mu_{s}$ does not preserves any fibre, and if $s\neq
k\bmod 2$, then $\mu_{s}$ preserves exactly two antipodal fibres.

###### Proof.

The proof is straightforward and left to the reader. ∎

The third type of automorphism is, for each $s\in\mathbb{Z}_{n}$, defined by

$\tau_{s}\cdot(i,x)=\begin{cases}(i,x^{s-i}),\quad&\text{if
}i\in\\{s,s-1,s-2,\dots,s-k+1\\},\\\ (i,x),&\text{otherwise,}\end{cases}$

where $x^{j}$ denotes the bitstring $x$ with bit $x_{j}$ flipped. Thus
$\tau_{s}$ flips bit $x_{s-i}$ of the bitstring component of every vertex in
$\mathcal{F}_{i}$ if $i\leq s\leq i+k-1$, and acts trivially on
$\mathcal{F}_{i}$ otherwise. Equivalently, vertices in $\mathcal{F}_{i}$ have
their bitstring components altered only by
$\tau_{i},\tau_{i+1},\dots,\tau_{i+k-1}$. Clearly each $\tau_{s}$ has order
$2$ and $\tau_{s},\tau_{t}$ commute for all $s,t\in\mathbb{Z}_{n}$. Hence the
subgroup of $\operatorname{Aut}(\operatorname{PX}(n,k))$ generated by these
automorphisms satisfies
$K=\langle\tau_{0},\tau_{1},\tau_{2},\dots,\tau_{n-1}\rangle\simeq\mathbb{Z}_{2}^{n}$.
Each $\tau\in K$ can be represented by

$\tau=\tau_{0}^{u_{0}}\tau_{1}^{u_{1}}\tau_{2}^{u_{2}}\cdots\tau_{n-1}^{u_{n-1}},$

where $u_{m}\in\\{0,1\\}$ for each $m\in\mathbb{Z}_{n}$. It is easy to verify
that $\rho^{-1}\tau_{s}\rho=\tau_{s+1}$ and $\mu\tau_{s}\mu=\tau_{k-1-s}$, so
$K$ is a normal subgroup of the group generated by $\rho,\mu$ and
$\tau_{0},\dots\tau_{n-1}$.

Let $\mathcal{A}=K\rtimes\langle\rho,\mu\rangle=K\rtimes D_{n}$. Then if
$\alpha\in\mathcal{A}$, $\alpha=\tau\delta$ for some $\tau\in K$ and
$\delta\in\langle\rho,\mu\rangle=D_{n}$. Praeger and Xu showed in [14] that
for all $n\neq 4$, $\mathcal{A}=\operatorname{Aut}(\operatorname{PX}(n,k))$,
while for $n=4$, $\mathcal{A}$ is a proper subgroup of
$\operatorname{Aut}(\operatorname{PX}(4,k))$.

Note that under any $\alpha\in\mathcal{A}$, vertices in the same fibre will be
mapped to vertices in the same fibre. In other words, the fibres form a block
system for the action of $\mathcal{A}$ on $\operatorname{PX}(n,k)$. From [15],
the induced action of $\alpha=\tau\delta\in\mathcal{A}$ on the fibres of
$\operatorname{PX}(n,k)$ is $\alpha(\mathcal{F}_{i})=\mathcal{F}_{\delta(i)}$,
where $\delta(i)$ is simply the action of the dihedral group element
$\delta\in D_{n}$ on $i\in V(C_{n})=\mathbb{Z}_{n}$. Since any
$\tau=\tau_{0}^{u_{0}}\tau_{1}^{u_{1}}\tau_{2}^{u_{2}}\cdots\tau_{n-1}^{u_{n-1}}\in
K$ preserves fibres, for any $\alpha=\tau\delta\in\mathcal{A}$ and $(i,x)\in
V$, we have

$\alpha\cdot(i,x)=\tau\cdot(\delta\cdot(i,x))=\tau\cdot(\delta(i),y)=(\delta(i),z),$

where $y=x$ if $\delta$ is a rotation $\rho^{s}$, $y=x^{-}$ if $\delta$ is a
reflection $u_{s}$, and for all $j\in\mathbb{Z}_{k}$, $z_{j}=y_{j}+1$ if
$u_{\delta(i)-j}=1$ and $z_{j}=y_{j}$ otherwise.

##  3 Determining and Distinguishing $\operatorname{PX}(n,1)$

For any vertex $v$ in a graph $G=(V,E)$, the (open) neighborhood of $v$ is
$N(v)=\\{u:\\{u,v\\}\in E\\}$. Distinct vertices $x$ and $y$ are (nonadjacent)
twins if and only if $N(x)=N(y)$. Twins are relevant to notions of graph
symmetry because if $x$ and $y$ are twins, then the map that interchanges $x$
and $y$ and fixes all other vertices is a graph automorphism.

######  Theorem 1.

For $k=1$, two distinct vertices in $\operatorname{PX}(n,1)$ are twins if and
only if either they are in the same fibre, or $n=4$ and they are in antipodal
fibres. For $k\geq 2$, $\text{PX}(n,k)$ is twin-free.

###### Proof.

First assume $k=1$. For any $i\in\mathbb{Z}_{n}$,
$\mathcal{F}_{i}=\\{(i,0),(i,1)\\}$. By definition,

$N((i,0))=\\{(i+1,0),(i+1,1),(i-1,0),(i-1,1)\\}=\mathcal{F}_{i+1}\cup\mathcal{F}_{i-1}=N((i,1)).$

Hence $(i,0)$ and $(i,1)$ are twins. More generally, $(i,x)$ and $(j,y)$ are
twins if and only if
$\mathcal{F}_{i+1}\cup\mathcal{F}_{i-1}=\mathcal{F}_{j+1}\cup\mathcal{F}_{j-1}$,
or equivalently, as subsets of $\mathbb{Z}_{n}$,
$\\{i+1,i-1\\}=\\{j+1,j-1\\}$. If $i\neq j$, then $i+1=j-1$ and $i-1=j+1$.
This implies $i-j=2=-2$in $\mathbb{Z}_{n}$. Since $n\geq 3$, we can conclude
$n=4$ and $\mathcal{F}_{i}$ and $\mathcal{F}_{j}$ are antipodal fibres.

Next assume $k\geq 2$. Let $u$ and $v$ be distinct vertices in
$\operatorname{PX}(n,k)$ such that $N(u)=N(v)$. Let $u=(i,axb)$ and
$v=(j,cyd)$ for some $i,j\in\mathbb{Z}_{n}$, $a,b,c,d\in\\{0,1\\}$, and
$y,x\in\mathbb{Z}_{2}^{k-2}$ (where $y$ and $x$ are empty strings if $k=2$).
By definition, $N(u)=\\{(i+1,xb0),(i+1,xb1),(i-1,0ax),(i-1,1ax)\\}$ and
$N(v)=\\{(j+1,yd0),(j+1,yd1),(j-1,0cy),(j-1,1cy)\\}.$ Since $N(u)$ consists of
two vertices in each of $\mathcal{F}_{i+1}$ and $\mathcal{F}_{i-1}$, and
$N(v)$ consists of two vertices in each of $\mathcal{F}_{j+1}$ and
$\mathcal{F}_{j-1}$, $\\{i+1,i-1\\}=\\{j+1,j-1\\}$.

Suppose $i=j\bmod n$. Comparing neighbors in
$\mathcal{F}_{i+1}=\mathcal{F}_{j+1}$ with the same final bit gives $xb0=yd0$
and $xb1=yd1$. Hence $xb=yd$ in $\mathbb{Z}_{2}^{k-1}$. An analogous argument
can be used in $\mathcal{F}_{i-1}$ to show that $ax=cy$ in
$\mathbb{Z}_{2}^{k-1}$. Thus $axb=cyd$ in $\mathbb{Z}_{2}^{k}$. Since $i=j$ in
$\mathbb{Z}_{n}$, $(i,axb)=(j,cyd)$ and so $u=v$, contradicting the assumption
that $u$ and $v$ are distinct.

Alternatively, if $i\neq j\bmod n$, then as argued earlier in this proof,
$n=4$ and $i-1=j+1\bmod n$. Hence
$N(u)\cap\mathcal{F}_{i-1}=N(v)\cap\mathcal{F}_{j+1}$, so

$\\{(i-1,0ax),(i-1,1ax)\\}=\\{(j+1,yd0),(j+1,yd1)\\}.$

Since $x$ and $y$ cannot be simultaneously both $0$ and $1$, this is
impossible. ∎

Figure 2 depicts two Praeger-Xu graph with twins. Note that every vertex of
$\operatorname{PX}(4,1)$ is in a set of $t=4$ mutual twins, while for any
$n\geq 3,n\neq 4$, every vertex of $\operatorname{PX}(n,1)$ is in a set of
$t=2$ mutual twins.

(a) $\operatorname{PX}(6,1)$

(b) $\operatorname{PX}(4,1)$.

Figure 2: Two Praeger-Xu graphs with $k=1$.

For any graph $G=(V,E)$, can define an equivalence relation on $V$ by $x\sim
y$ if and only if $x$ and $y$ are twins. The corresponding _twin quotient
graph_ $\widetilde{G}$ has as its vertex set the set of equivalence classes
$[x]=\\{y\in V(G):x\sim y\\}$, with $\\{[x],[z]\\}\in E(\widetilde{G})$ if and
only if there exist $p\in[x]$ and $q\in[z]$ such that $\\{p,q\\}\in E(G)$.
(Note that by definition of the twin relation, $\\{[x],[z]\\}\in
E(\widetilde{G})$ if and only if for all $p\in[x]$ and $q\in[z]$,
$\\{p,q\\}\in E(G)$.) The symmetry parameters of the twin quotient graph
$\widetilde{G}$ can be used to give information about the symmetry parameters
of $G$.

A subset $T\subseteq V(G)$ that contains all but one of the vertices from each
equivalence class of twin vertices is called a _minimum twin cover_ of $G$. In
2020, Boutin et al. proved the following result.

######  Theorem 2.

[4, Theorem 19] Let $G$ be a graph with twin quotient graph $\widetilde{G}$.
Let $T$ be a minimum twin cover of $G$ and let $\widetilde{T}=\\{[u]:u\in
T\\}\subseteq V(\widetilde{G})$. Let $\widetilde{S}$ be a determining set for
$\widetilde{G}$ containing $\widetilde{T}$. Let $R=\\{x\in
V(G):[x]\in\widetilde{S}\setminus\widetilde{T}\\}$. Then $S=T\cup R$ is a
determining set for $G$. Furthermore, if $\widetilde{S}$ is of minimum size
among determining sets for $\widetilde{G}$ that contain $\widetilde{T}$, then
$S$ is a minimum determining set for $G$.

For distinguishing number, we have the following result from Cockburn and
Loeb.

######  Theorem 3.

[8, Theorem 2] Let $G$ be a graph in which every vertex is in a set of $t$
mutual twins. If $\operatorname{Dist}(\widetilde{G})=\widetilde{d}$, then
$\operatorname{Dist}(G)=d$, where $d$ is the smallest positive integer such
that $\binom{d}{t}\geq\widetilde{d}$.

These theorems can be used to find the symmetry parameters of all Praeger-Xu
graphs with twins, $\operatorname{PX}(n,1)$.

######  Theorem 4.

For $n=4$, $\operatorname{Det}(\operatorname{PX}(4,1))=6$ and
$\operatorname{Dist}(\operatorname{PX}(4,1))=5$. For all $n\neq 4$,
$\operatorname{Det}(\operatorname{PX}(n,1))=n$ and
$\operatorname{Dist}(\operatorname{PX}(n,1))=3$.

###### Proof.

For $n=4$, there are only two equivalence class under the twin relation,
namely $[(0,0)]=\mathcal{F}_{0}\cup\mathcal{F}_{2}$ and
$[(1,0)]=\mathcal{F}_{1}\cup\mathcal{F}_{3}$, so the twin quotient graph is
$\widetilde{\operatorname{PX}}(4,1)=K_{2}$. In this case,
$T=\\{(0,0),(0,1),(2,0),(1,0),(1,1),(3,0)\\}$ is a minimum twin cover with
$\widetilde{T}=V(\widetilde{\operatorname{PX}}(4,1))$. The only determining
set $\widetilde{S}$ of the twin quotient graph containing $\widetilde{T}$ is
the entire vertex set. Hence by Theorem 2, $T$ is a minimum determining set
and so $\operatorname{Det}(\operatorname{PX}(4,1))=6$. Since every vertex of
$\operatorname{PX}(4,1)$ is in a set of $t=4$ mutual twins and
$\operatorname{Dist}(K_{2})=2$, by Theorem 3,
$\operatorname{Dist}(\operatorname{PX}(4,1))=5$.

Next assume $n\neq 4$. In this case, the equivalence classes under the twin
relation are the fibres of $\operatorname{PX}(n,1)$ and so
$T=\\{(i,0):i\in\mathbb{Z}_{n}\\}$ is a minimum twin cover of
$\operatorname{PX}(n,1)$. Additionally, every vertex in
$V(\operatorname{PX}(n,1))$ belongs to one of these fibres, so
$V(\widetilde{\operatorname{PX}}(n,1))=\widetilde{T}$. Again the only
determining set $\widetilde{S}$ of the twin quotient graph containing
$\widetilde{T}$ is the entire vertex set and so by Theorem 2, $T$ is a minimum
determining set. Thus $\operatorname{Det}(\operatorname{PX}(n,1))=|T|=n$.

Since every fibre in $\operatorname{PX}(n,1)$ is a vertex in
$\widetilde{\operatorname{PX}}(n,i)$, and vertices in $\mathcal{F}_{i}$ are
adjacent only to vertices in $\mathcal{F}_{i+1}$ and $\mathcal{F}_{i-1}$,
$\widetilde{\operatorname{PX}}(n,1)=C_{n}$. Hence,
$\widetilde{d}=\text{Dist}(\widetilde{\operatorname{PX}}(n,1))=\text{Dist}(C_{n})=3$
if $n\in\\{3,5\\}$, and $\widetilde{d}=2$ if $n\geq 6$. Since each vertex is
in a set of $t=2$ twins, by Theorem 3, $d$ is the smallest integer such that
${d\choose 2}\geq 3$ if $n\in\\{3,5\\}$, and $d$ is the smallest integer such
that ${d\choose 2}\geq 2$ if $n\geq 6$. In both cases, $d=3$. ∎

##  4 Determining $\operatorname{PX}(n,k)$, $k\geq 2$

In this section, we find the determining number for twin-free Praeger-Xu
graphs. Recall from Section 2 that for $n\neq 4$,
$\mathcal{A}=K\rtimes\langle\rho,\mu\rangle=\operatorname{Aut}(\operatorname{PX}(n,k))$,
whereas for $n=4$, $\mathcal{A}$ is a proper subgroup of
$\operatorname{Aut}(\operatorname{PX}(4,k))$. We begin with a lemma that
applies to all Praeger-Xu graphs and apply it to the general case $n\neq 4$.
We then consider the exceptional cases $\operatorname{PX}(4,2)$ and
$\operatorname{PX}(4,3)$.

######  Lemma 2.

Let $i\in\mathbb{Z}_{n}$, $S_{i}\subseteq\mathcal{F}_{i}$ and
$\tau=\tau_{0}^{u_{0}}\cdots\tau_{n-1}^{u_{n-1}}\in K$. If $\tau(S_{i})=S_{i}$
and $|S_{i}|$ is odd, then $\tau$ acts trivially on $\mathcal{F}_{i}$;
equivalently,

$u_{i}=u_{i+1}=\dots=u_{i+k-1}=0.$

###### Proof.

Assume $\tau(S_{i})=S_{i}$ and that $\tau$ acts nontrivially on
$\mathcal{F}_{i}$. Let $s\in S\subseteq\mathcal{F}_{i}$, so by assumption,
$\tau\cdot s\in S_{i}$. Since every element in $K\simeq\mathbb{Z}_{2}^{n}$ has
order $2$, $\tau\cdot(\tau\cdot s)=\tau^{-1}\cdot(\tau\cdot s)=s.$
Additionally, since $\tau$ acts nontrivially on every vertex of
$\mathcal{F}_{i}$, $s\neq\tau\cdot s$. Thus, $S$ can be partitioned into pairs
of the form $\\{s,\tau\cdot s\\}$, implying that $S_{i}$ has an even number of
vertices in total. ∎

######  Theorem 5.

For $n\neq 4$,

$\operatorname{Det}(\operatorname{PX}(n,k))=\begin{cases}\lceil\frac{n}{k}\rceil,\quad&\text{
if }k\neq\frac{n}{2},\\\ \lceil\frac{n}{k}\rceil+1=3,&\text{ if
}k=\frac{n}{2}.\end{cases}$

###### Proof.

First suppose $k\neq\frac{n}{2}$. Let $S\subset V(\operatorname{PX}(n,k))$
such that $|S|=\lceil\frac{n}{k}\rceil-1$, and assume $S$ is a determining set
for $\operatorname{PX}(n,k)$. The set of indices of the fibres containing
elements of $S$ is

$I_{S}=\\{i\in\mathbb{Z}_{n}\mid
S\cap\mathcal{F}_{i}\neq\emptyset\\}=\\{i_{1},i_{2},\dots,i_{s}\\},$

where $0\leq i_{1}<i_{2}\dots<i_{s}\leq n-1$. Then the number of fibres in the
gaps between these fibres are
$i_{2}-i_{1}-1,i_{3}-i_{2}-1,\dots,n+i_{1}-i_{s}-1$. If $i_{p+1}-i_{p}-1\geq
k$ for some $i_{p},i_{p+1}\in S$ , then $\tau_{i_{p+1}-1}$ is a nontrivial
automorphism that fixes $S$, contradicting the assumption that $S$ is a
determining set. Thus each gap contains at most $k-1$ fibres. Since every
fibre either contains a vertex in $S$ or is in a gap between two such fibres,
the total number of fibres satisfies

$|I_{S}|+|I_{S}|(k-1)=|I_{S}|k\ \leq|S|k=(\lceil\tfrac{n}{k}\rceil-1)k<n,$

a contradiction. Thus,
$\operatorname{Det}(\operatorname{PX}(n,k))>\lceil\frac{n}{k}\rceil-1$.

We claim
$S=\big{\\{}v_{ik}\in\mathcal{F}_{ik}:i\in\\{0,1,\dots,\lceil\tfrac{n}{k}\rceil-1\\}\big{\\}},$
where $v_{ik}$ is any vertex in $\mathcal{F}_{ik}$, is a determining set for
$\text{PX}(n,k)$. Let
$\alpha=\tau\delta\in\mathcal{A}=\operatorname{Aut}(\operatorname{PX}(n,k))$
such that $\alpha$ fixes every vertex in $S$. Since $k\neq\tfrac{n}{2}$,
$\mathcal{F}_{0}$ and $\mathcal{F}_{k}$ are non-antipodal fibres. Since the
induced action of $\alpha$ on the fibres is an element of $D_{n}$ that fixes
non-antipodal vertices $0$ and $k$ in $C_{n}$, $\delta=\text{id}$.

Next we show that
$\tau=\tau_{0}^{u_{0}}\tau_{1}^{u_{1}}\cdots\tau_{n-1}^{u_{n-1}}=\text{id}$.
Let $S_{0}=S\cap\mathcal{F}_{0}$; note that $|S_{0}|=1$ is odd. Since $\tau$
fixes every vertex in $S$, $\tau(S_{0})=S_{0},$ and so by Lemma 2,
$u_{0}=u_{1}=\dots=u_{k+1}=0$. Applying the same logic to
$S_{k}=S\cap\mathcal{F}_{k}$, we get $u_{k}=u_{k+1}=\dots=u_{2k-1}=0$.
Iterating this argument for $S_{ik}$ for all
$i\in\\{0,1,\dots\lceil\frac{n}{k}\rceil-1\\}$, we conclude
$u_{0}=\dots=u_{n-1}=0$. Thus $\tau=\text{id}$. By definition, $S$ is a
determining set and so
$\operatorname{Det}(\operatorname{PX}(n,k))\leq|S|=\lceil\frac{n}{k}\rceil$.

Now suppose $k=\frac{n}{2}$. Assume $S$ is a determining set of cardinality
$2$. Since $\operatorname{PX}(n,k)$ is vertex-transitive, we can assume
without loss of generality that $S=\\{z=(0,00\cdots 0),v=(i,x)\\}$. There are
three cases: $i=0$, $i=k=\frac{n}{2}$, or $i\neq 0$ and $i\neq k=\frac{n}{2}$.

For the first case, assume $i=0$, so both $z,v\in\mathcal{F}_{0}$. Then since
$\tau_{n-1}$ affects $\mathcal{F}_{i}$ if and only if
$i\in\\{k=\frac{n}{2},\frac{n}{2}+1,\dots,n-1\\}$, and $0$ is not in that set,
$\tau_{n-1}$ is a nontrivial automorphism that fixes $S$, a contradiction.

For the second case, assume $i=k=\frac{n}{2}$. Then $z$ and $v$ are in
antipodal fibres. If we we apply the reflection $\mu$ to $S$, we get

$\mu\big{(}S\big{)}=\big{\\{}(0,(00\cdots
0)^{-}),(-k,x^{-})\big{\\}}=\big{\\{}(0,00\cdots 0),(k,x^{-})\big{\\}}.$

For each $m$ such that $x_{m}\neq(x^{-})_{m}$, the automorphism $\tau_{k+m}\in
K$ flips this bit in the bitstring component of every vertex in
$\mathcal{F}_{k}$, but has no effect on the vertices in $\mathcal{F}_{0}$. Let
$\tau=\tau_{0}^{u_{0}}\tau_{1}^{u_{1}}\cdots\tau_{n-1}^{u_{n-1}}$ where
$u_{k+m}=1$ if $x_{m}\neq(x^{-})_{m}$ and $0$ otherwise. Then $\zeta=\tau\mu$
fixes both $z$ and $v$, contradicting our assumption that $S$ is a determining
set.

In the third case, $i\neq 0$ and $i\neq k=\frac{n}{2}$, so we can assume that
in $\mathbb{Z}$, either $0<i<k$ or $k<i<n$. In the first case, $\tau_{n-1}$
fixes both $z$ and $v$, and in the second, $\tau_{i-1}$ fixes both $z$ and
$v$. Hence, $S$ is not a determining set for $\operatorname{PX}(n,k)$. As we
have covered all possible cases, we conclude
$\operatorname{Det}(\operatorname{PX}(n,k))>2$.

Finally, let $S=\\{v_{0},v_{1},v_{k}\\}$ where $v_{0}\in\mathcal{F}_{0}$,
$v_{1}\in\mathcal{F}_{1}$ and $v_{k}\in\mathcal{F}_{k}$ and assume
$\alpha=\tau\delta$ fixes $S$. The induced action of $\alpha$ on the fibres
corresponds to an element of the dihedral group that fixes non-antipodal
vertices $0$ and $1$ in $C_{n}$, so $\delta=\text{id}$. Next,
$\tau=\tau_{0}^{u_{0}}\cdots\tau_{n-1}^{u_{n-1}}$ fixes one vertex in each of
$\mathcal{F}_{0}$ and $\mathcal{F}_{k}$, so by Lemma 2,
$u_{0}=\dots=u_{k-1}=u_{k}=\dots=u_{2k-1}=u_{n-1}=0$. Thus $\tau=\text{id}$.
By definition, $S$ is a determining set for $\operatorname{PX}(n,k)$ so
$\operatorname{Det}(\operatorname{PX}(n,k))\leq|S|=3$. Thus
$\operatorname{Det}(\operatorname{PX}(n,k))=3$. ∎

We now turn our attention to the exceptional cases $\operatorname{PX}(4,2)$
and $\operatorname{PX}(4,3)$. It is stated without proof in [14] that
$Q_{4}\cong\operatorname{PX}(4,2)$; we provide an explicit isomorphism. A
bitstring $x$ is _even_ if $x$ has an even number of ones, and $x$ is _odd_
otherwise. Define $\varphi:V(Q_{4})\rightarrow V(\operatorname{PX}(4,2))$ by

$\varphi(x_{0}x_{1}x_{2}x_{3})=\begin{cases}(j,x_{1}x_{3}),\quad&\text{ if
}j\text{ is odd},\\\ (j,x_{3}x_{1}),&\text{ if }j\text{ is even},\end{cases}$

where

$j=\begin{cases}0,\quad&\text{ if }x_{0}x_{1}\text{ and }x_{2}x_{3}\text{ are
both odd},\\\ 1,&\text{ if }x_{0}x_{1}\text{ is odd and }x_{2}x_{3}\text{ is
even},\\\ 2,&\text{ if }x_{0}x_{1}\text{ and }x_{2}x_{3}\text{ are both
even},\\\ 3,&\text{ if }x_{0}x_{1}\text{ is even and }x_{2}x_{3}\text{ is
odd}.\end{cases}$

Figure 3 is a drawing of $Q_{4}$, with vertices positioned as they would be in
a canonical drawing of $\operatorname{PX}(4,2)$, as explained at the beginning
of Section 2.

Figure 3: $Q_{4}$ is isomorphic to $\operatorname{PX}(4,2)$.

######  Proposition 1.

$\operatorname{Det}(\operatorname{PX}(4,2))=3,\operatorname{Dist}(\operatorname{PX}(4,2))=2\text{
and }\rho(\operatorname{PX}(4,2))=5.$

###### Proof.

This follows immediately from previous work on the symmetry parameters of
$Q_{4}$. By Theorem 3 from [6],

$\operatorname{Det}(\operatorname{PX}(4,2))=\operatorname{Det}(Q_{4})=\lceil\log_{2}4\rceil+1=2+1=3.$

Notably, this expression agrees with the formula given in Theorem 5 because
$\lceil\frac{4}{2}\rceil+1=2+1=3$. By Theorem 5 from [3],
$\operatorname{Dist}(\operatorname{PX}(4,2))=\operatorname{Dist}(Q_{4})=2$; by
Theorem 11 from [7], $\rho(\operatorname{PX}(4,2))=\rho(Q_{4})=5$. ∎

######  Proposition 2.

$\operatorname{Det}(\operatorname{PX}(4,3))=2=\lceil\frac{4}{3}\rceil.$

###### Proof.

From [14], $\mathcal{A}=K\rtimes\langle\rho,\mu\rangle$ is a proper subgroup
of $\operatorname{Aut}(\operatorname{PX}(4,3))$ of index $2$. The proof of
Theorem 5 can be used when $(n,k)=(4,3)$ to show that the only
$\alpha\in\mathcal{A}$ that fixes two vertices from non-antipodal fibres is
the identity. However, more care must be taken when choosing the two vertices.
For example, there is a nontrivial automorphism
$\xi\in\operatorname{Aut}(\operatorname{PX}(4,3))$ that fixes both elements of
$S=\\{(0,000),(3,000)\\}$. More precisely, as a permutation $\xi$ is the
product of the disjoint $2$-cycles in Table 2. Unlike for any
$\alpha\in\mathcal{A}$, the fibres do not constitute a block system for $\xi$.
However, if we partition each fibre into vertices whose bitstrings are
palindromic ($x=x^{-}$) and vertices whose bitstrings are nonpalindromic
($x\neq x^{-}$), these half-fibres constitute a block system for $\xi$.

within $\mathcal{F}_{0}$, $x=x^{-}$ | ((0,010), (0,101)) |
---|---|---
within $\mathcal{F}_{2}$, $x\neq x^{-}$ | ((2,001), (2,110)) |
between $\mathcal{F}_{0}$, $x\neq x^{-}$ and $\mathcal{F}_{2}$, $x=x^{-}$ | ((0,001), (2,000)), | ((0,100), (2,010))
| ((0,011), (2,101)), | ((0,110), (2,111))
within $\mathcal{F}_{1}$, $x\neq x^{-}$ | ((1,100), (1,011)) |
within $\mathcal{F}_{3}$, $x=x^{-}$ | ((3,010), (3,101)) |
between $\mathcal{F}_{1}$, $x=x^{-}$ and $\mathcal{F}_{3}$, $x\neq x^{-}$ | ((1,000), (3,100)), | ((1,010), (3,001))
| ((1,101), (3,110)), | ((1,111), (3,011))
Table 2: Disjoint $2$-cycles of
$\xi\in\operatorname{Aut}(\operatorname{PX}(4,3))$.

Implicitly $\xi$ has eight fixed points, with two in each fibre, namely
$(0,000)$, $(0,111)$, $(1,001)$, $(1,110)$, $(2,100)$, $(2,001)$, $(3,000)$
and $(3,111)$. Since $\mathcal{A}$ has index $2$ in
$\operatorname{Aut}(\operatorname{PX}(4,3))$, every automorphism of
$\operatorname{PX}(4,3)$ is in one of the two cosets, $\mathcal{A}$ and
$\mathcal{A}\xi$.

Next we show that $S^{\prime}=\\{(0,000),(3,001)\\}$ is a determining set. The
two vertices in $S^{\prime}$ are from non-antipodal fibres, so no nontrivial
automorphism in $\mathcal{A}$ fixes both vertices in $S^{\prime}$. Table 2
shows that $\xi$ clearly does not fix $(3,001)$; we must also show that no
other automorphism in the coset $\mathcal{A}\xi$ fixes $S^{\prime}$.

Assume there exists $\beta\in\mathcal{A}$ such that $\beta\circ\xi$ fixes
$S^{\prime}$. Then $(0,000)=\beta\circ\xi\cdot(0,000)=\beta\cdot(0,000)$ and
$(3,001)=\beta\circ\xi\cdot(3,001)=\beta\cdot(1,010)$. The induced action of
$\beta$ on the fibres fixes $\mathcal{F}_{0}$ and takes $\mathcal{F}_{1}$ to
$\mathcal{F}_{3}$, so by Lemma 1,
$\beta=\tau\circ\mu=\tau_{0}^{u_{0}}\tau_{1}^{u_{1}}\tau_{2}^{u_{2}}\tau_{3}^{u_{3}}\mu$.
Since $\beta$ and $\mu$ both fix $(0,000)$, so must $\tau$ and by Lemma 2,
$u_{0}=u_{1}=u_{2}=0$. However, because $\tau_{3}$ can only affect the $0$-th
bit of the bitstring component of a vertex in $\mathcal{F}_{3}$, no value of
$u_{3}$ satisfies
$(3,001)=\beta\cdot(1,010)=\tau_{3}^{u_{3}}\mu\cdot(1,010)=\tau_{3}^{u_{3}}\cdot(3,010)$.
∎

The following theorem summarizes our results on the determining number of
twin-free Praeger-Xu graphs.

######  Theorem 6.

For all $n\geq 3$ and $2\leq k<n$,

$\operatorname{Det}(\operatorname{PX}(n,k))=\begin{cases}\lceil\frac{n}{k}\rceil,\quad&\text{
if }k\neq\frac{n}{2},\\\ \lceil\frac{n}{k}\rceil+1=3,&\text{ if
}k=\frac{n}{2}.\end{cases}$

##  5 Interchangeable Vertices in $\operatorname{PX}(n,k)$

As mentioned in Section 3, if two vertices in a graph are twins, then the map
that interchanges them and leaves all vertices fixed is a graph automorphism.
By Theorem 1, if $k\geq 2$, then $\operatorname{PX}(n,k)$ is twin-free, but we
will find it useful to identify when two vertices can be interchanged by an
automorphism, regardless of its action on other vertices.

######  Definition 2.

Distinct vertices $u,v$ in a graph $G$ are interchangeable if and only if
there exists $\alpha\in\operatorname{Aut}(G)$ such that $\alpha\cdot u=v$ and
$\alpha\cdot v=u$.

There are some situations where it is easy to find an automorphism
interchanging vertices $u=(i,x)$ and $v=(j,y)$ in $\operatorname{PX}(n,k)$. If
$i=j$, there exists $\tau=\tau_{0}^{u_{0}}\cdots\tau_{n-1}^{u_{n-1}}\in K$
that flips exactly the right bits in bitstring components of vertices in
$\mathcal{F}_{i}$. More precisely, for each $t\in\\{0,1,\dots,k-1\\}$, if
$x_{t}\neq y_{t}$, set $u_{i+t}=1$, and otherwise set $u_{i+t}=0$. The values
of $u_{m}$ for any $m\in\mathbb{Z}_{n}$ not of the form $i+t$ do not affect
the action of $\tau$ on $u$ and $v$. If $i\neq j$, then we can find
$\delta\in\langle\rho,\mu\rangle$ such that the induced action of $\delta$ on
the fibres interchanges $\mathcal{F}_{i}$ and $\mathcal{F}_{j}$; we can then
look for $\tau=\tau_{0}^{u_{0}}\cdots\tau_{n-1}^{u_{n-1}}\in K$ so that $\tau$
flips exactly the right bits in both $\mathcal{F}_{i}$ and $\mathcal{F}_{j}$
to ensure that $\tau\delta$ interchanges $u$ and $v$. If $\mathcal{F}_{i}$ and
$\mathcal{F}_{j}$ are far enough apart, then we can set the values
$u_{i},u_{i+1},\dots u_{i+k-1}$ and $u_{j},u_{j+1},\dots u_{j+k-1}$
independently. However, if
$M=\big{\\{}i,i+1,i+2,\dots,i+k-1\big{\\}}\cap\big{\\{}j,j+1,j+2,\dots,j+k-1\big{\\}}\neq\emptyset$,
then for any $m\in M$, $\tau_{m}$ affects both vertices in $\mathcal{F}_{i}$
and $\mathcal{F}_{j}$ and there is potential for conflict.

######  Lemma 3.

Let $u=(i,x),v=(j,y)\in V(\operatorname{PX}(n,k))$ and let

$M=\big{\\{}i,i+1,i+2,\dots,i+k-1\big{\\}}\cap\big{\\{}j,j+1,j+2,\dots,j+k-1\big{\\}}\subseteq\mathbb{Z}_{n}.$

Then $u$ and $v$ are interchangeable by some $\alpha\in\mathcal{A}$ if and
only if one of the following holds:

  1. (1)

$j=i$,

  2. (2)

$j\neq i$ and for all $m\in M$, $(x^{-})_{m-j}=y_{m-j}$ if and only if
$(y^{-})_{m-i}=x_{m-i}$,

  3. (3)

$j=i+\frac{n}{2}$ and for all $m\in M$, $x_{m-j}=y_{m-j}$ if and only if
$y_{m-i}=x_{m-i}$.

###### Proof.

Assume $u$ and $v$ are interchangeable by $\alpha=\tau\delta\in\mathcal{A}$,
but neither (1) nor (2) holds. Then $j\neq i$ and for some $m\in M$, either
$(x^{-})_{m-j}=y_{m-j}$ but $(y^{-})_{m-i}\neq x_{m-i}$, or $(x^{-})_{m-j}\neq
y_{m-j}$ but $(y^{-})_{m-i}=x_{m-i}$. As usual, either $\delta=\rho^{s}$ or
$\delta=\mu_{s}$ for some $s\in\mathbb{Z}_{n}$.

If $\delta=\mu_{s}$, then $\mu_{s}\cdot u=(j,x^{-})$ and $\mu_{s}\cdot
v=(i,y^{-})$, and hence $\tau\cdot(j,x^{-})=(j,y)$ and
$\tau\cdot(i,y^{-})=(i,x)$, where
$\tau=\tau_{0}^{u_{0}}\tau_{1}^{u_{1}}\cdots\tau_{n-1}^{u_{n-1}}$. If
$(x^{-})_{m-j}=y_{m-j}$ and $(y^{-})_{m-i}\neq x_{m-i}$, then since $\tau_{m}$
flips the $(m-j)$-th bit of the bitstrings in $\mathcal{F}_{j}$, $u_{m}=0$.
However, $\tau_{m}$ flips the $(m-i)$-th bit of bitstrings in
$\mathcal{F}_{i}$, so $u_{m}=1$, a contradiction. A completely analogous
argument works if $(x^{-})_{m-j}\neq y_{m-j}$ and $(y^{-})_{m-i}=x_{m-i}$.
Thus, $\delta=\rho^{s}$.

Since $\rho^{s}\cdot u=(i+s,x)$ and $\rho^{s}\cdot v=(j+s,y)$, and $\tau$
fixes every fibre, $i+s=j$ and $j+s=i$. Since we are assuming $i\neq j$,
$s=\frac{n}{2}$, so $j=i+\frac{n}{2}$. Let $m\in M$, and assume
$x_{m-j}=y_{m-j}$. Since $\tau\cdot(j,x)=(j,y)$, $\tau$ must not flip the
$(m-j)$-th bit of the bitstrings of $\mathcal{F}_{j}$, so $u_{m}=0$. That
means that $\tau$ must also not flip the $(m-i)$-th bit of the bitstrings of
$\mathcal{F}_{i}$, so since $\tau\cdot(i,y)=(i,x)$, $y_{m-i}=x_{m-i}$. A
completely analogous argument works if we assume $y_{m-i}=x_{m-i}$. Thus
condition (3) holds.

Conversely, we will show that if one of (1), (2) or (3) holds, then $u$ and
$v$ are interchangeable by some $\alpha\in\mathcal{A}$. First, assume (1)
holds, so $j=i$. As noted in the paragraph before the statement of this lemma,
there is some $\tau\in K\subset\mathcal{A}$ that interchanges $u$ and $v$.

Next, assume (2) holds, so $j\neq i$ and for all $m\in M$,
$(x^{-})_{m-j}=y_{m-j}$ if and only if $(y^{-})_{m-i}=x_{m-i}$. Let
$\tau=\tau_{0}^{u_{0}}\tau_{1}^{u_{1}}\cdots\tau_{n-1}^{u_{n-1}}\in K$, where
for each $s\in\mathbb{Z}_{n}$, $u_{s}=1$ if $(x^{-})_{s-j}\neq y_{s-j}$ and
$(y^{-})_{s-i}\neq x_{s-i}$ and $u_{s}=0$ otherwise. Hence, in
$\mathcal{F}_{j}$, $\tau$ flips the bits in every position that $x^{-}$ and
$y$ differ and no others, and in $\mathcal{F}_{i}$, $\tau$ flips the bits in
every position that $y^{-}$ and $x$ differ and no others. By Lemma 1, there
exists $\mu_{s}\in\langle\rho,\mu\rangle$ such that $\mu_{s}\cdot u=(j,x^{-})$
and $\mu_{s}\cdot v=(i,y^{-})$. Let $\alpha=\tau\mu_{s}\in\mathcal{A}$. Then
$\alpha\cdot u=\tau\cdot(\mu_{s}\cdot u)=\tau\cdot(j,x^{-})=(j,y),$ and
$\alpha\cdot v=\tau\cdot(\mu_{s}\cdot v)=\tau\cdot(i,y^{-})=(i,x),$ so $u$ and
$v$ are interchangeable by $\alpha\in\mathcal{A}$.

Lastly, assume (3) holds, so $j=i+\frac{n}{2}$ and for all $m\in M$,
$x_{m-j}=y_{m-j}$ if and only if $y_{m-i}=x_{m-i}$. Let
$\tau=\tau_{0}^{u_{0}}\tau_{1}^{u_{1}}\cdots\tau_{n-1}^{u_{n-1}}\in K$, where
for each $s\in\mathbb{Z}_{n}$, $u_{s}=1$ if $x_{s-j}\neq y_{s-j}$ and
$u_{s}=0$ otherwise. By assumption, that also means that $u_{s}=1$ if
$y_{s-i}\neq x_{s-i}$ and $u_{s}=0$ otherwise. Hence, in both
$\mathcal{F}_{i}$ and $\mathcal{F}_{j}$, $\tau$ flips the bits in every
position that $x$ and $y$ differ, and no others. It is straighforward to
verify that $\alpha=\tau\rho^{n/2}\in\mathcal{A}$ interchanges $u$ and $v$. ∎

For example, let $u=(i,x)=(0,101),v=(j,y)=(1,001)\in
V(\operatorname{PX}(5,3))$. Then $M=\\{0,1,2\\}\cap\\{1,2,3\\}=\\{1,2\\}$.
Since $x^{-}=101$ and $y^{-}=100$, for $m=1$, $(x^{-})_{m-j}=1\neq 0=y_{m-j}$
and $(y^{-})_{m-i}=0=x_{m-i}$. Hence, by Lemma 3, $u$ and $v$ are not
interchangeable.

Note that it is possible for a pair of vertices to be interchangeable by two
different automorphisms. For example, $z=(0,000)$ and $v=(5,000)$ in
$\operatorname{PX}(10,3)$ satisfy both conditions (2) and (3), and so can be
interchanged using either a rotation or a reflection.

We will find it useful in the next section to identify which vertices of
$\operatorname{PX}(n,k)$ are interchangeable with $z=(0,00\cdots 0)$.

######  Corollary 1.

Let $v=(j,y)\in V(\operatorname{PX}(n,k))$ and let

$M=\big{\\{}0,1,2,\dots,k-1\big{\\}}\cap\big{\\{}j,j+1,j+2,\dots,j+k-1\big{\\}}.$

Then $z=(0,00\cdots 0)$ and $v$ are interchangeable by some
$\alpha\in\mathcal{A}$ if and only if one of the following holds:

  1. (1)

$j=0$,

  2. (2)

$j\neq 0$ and for all $m\in M$, $y_{m-j}=(y^{-})_{m}=y_{k-1-m}$,

  3. (3)

$j=\frac{n}{2}$ and for all $m\in M$, $y_{m-j}=y_{m}$.

To illustrate how vertex interchangeability can be used to compute symmetry
parameters, we consider the smallest twin-free Praeger-Xu graph.

######  Lemma 4.

Any two distinct vertices of $\operatorname{PX}(3,2)$ are interchangeable.

###### Proof.

By vertex-transitivity, it suffices to show that $z=(0,00)$ is interchangeable
with any vertex $v=(j,y)$. Since $n=3$ is odd, we need only check that
condition (2) of Corollary 1 holds. If $j=1$, then $M=\\{1\\}$ and
$y_{m-j}=y_{k-1-m}=y_{0}$. If $j=2$, then $M=\\{0\\}$ and
$y_{m-j}=y_{k-1-m}=y_{1}$. ∎

######  Theorem 7.

$\operatorname{Dist}(\operatorname{PX}(3,2))=2$ and
$\rho(\operatorname{PX}(3,2))=3$.

###### Proof.

Color the vertices in $R=\\{(0,00),(1,01),(2,00)\\}$ red and every other
vertex blue. Assume
$\alpha=\tau\delta\in\mathcal{A}=\operatorname{Aut}(\operatorname{PX}(3,2))$
preserves colors, where
$\tau=\tau_{0}^{u_{0}}\tau_{1}^{u_{1}}\tau_{2}^{u_{2}}$.

Suppose $\delta=\rho^{s}$ for some $s\in\\{1,2\\}$. If $s=1$, then
$\delta\cdot(1,01)=(2,01)$. Since $\alpha$ preserves colors,
$\tau\cdot(2,01)=(2,00)$, which implies $u_{0}=1$ and $u_{2}=0$. However, then
$\tau\delta\cdot(2,00)=\tau\cdot(0,00)=(0,1a)$ for some $a\in\mathbb{Z}_{2}$.
This contradicts our assumption that $\alpha$ preserves colors. If $s=2$, then
$\delta\cdot(1,01)=(0,01)$, and hence $u_{1}=1$ and $u_{0}=0$. A similar
contradiction arises because $\delta\cdot(2,00)=(1,00)$, and $u_{1}=1$ means
$\tau\cdot(1,00)=(1,1a)$ for some $a\in\mathbb{Z}_{2}$. Thus $\delta$ cannot
be a nontrivial rotation.

Suppose $\delta=\mu_{s}$ for some $s\in\mathbb{Z}_{3}$. By Lemma 1, $\delta$
preserves one fibre and interchanges the other two. If $\delta$ preserves
$\mathcal{F}_{0}$ and interchanges $\mathcal{F}_{1}$ and $\mathcal{F}_{2}$,
then $\delta\cdot(1,01)=(2,10)$. Since $\alpha$ preserves colors,
$\tau\cdot(2,10)=(2,00)$, so $u_{2}=1$. However, $\delta\cdot(2,00)=(1,00)$,
which implies $\tau\cdot(1,00)=(1,1a)$ for some $a\in\mathbb{Z}_{2}$, a
contradiction. Similar arguments apply to the remaining two cases. Since
$\delta$ is neither a nontrivial rotation nor a reflection,
$\delta=\text{id}$.

Since $\alpha$ preserves colors and fibres, $\tau$ preserves the one red
vertex in each fibre, so by Lemma 2, $u_{0}=u_{1}=u_{2}=0$. Hence,
$\alpha=\tau=\text{id}$, so this is a $2$-distinguishing coloring with smaller
color class of size $3$. Thus, $\operatorname{Dist}(\operatorname{PX}(3,2))=2$
and $\rho(\operatorname{PX}(3,2))\leq 3$.

To show $\rho(\operatorname{PX}(3,2)>2$, let $R=\\{u,v\\}\subset
V(\operatorname{PX}(3,2))$. Color the vertices in $R$ red and every other
vertex blue. By Lemma 4, $u$ and $v$ are interchangeable; any automorphism
interchanging them is a nontrivial color-preserving automorphism. Thus,
$\rho(\operatorname{PX}(3,2))>2$, so $\rho(\operatorname{PX}(3,2))=3$. ∎

##  6 Distinguishing $\operatorname{PX}(n,k)$, $k\geq 2$

We have already found the distinguishing parameters for a number of Praeger-Xu
graphs. Theorem 4 covers the case $k=1$; Theorem 7 covers
$\operatorname{PX}(3,2)$ and Proposition 1 covers $\operatorname{PX}(4,2)$.
The next result covers the exceptional case $\operatorname{PX}(4,3)$. The
remainder of this section covers the case $n\geq 5$ and $k\geq 2$.

######  Theorem 8.

$\operatorname{Dist}(\operatorname{PX}(4,3))=2$ and
$\rho(\operatorname{PX}(4,3))=3=\lceil\frac{4}{3}\rceil+1$.

###### Proof.

Color the vertices in $R=\\{(0,000),(2,000),(3,001)\\}$ red and all other
vertices blue. Suppose $\beta\in\operatorname{Aut}(\operatorname{PX}(4,3))$
preserves this coloring. Recall that
$\operatorname{Aut}(\operatorname{PX}(4,3))$ can be partitioned into the
cosets $\mathcal{A}$ and $\mathcal{A}\xi$. First assume $\beta=\alpha\xi$ for
some $\alpha\in\mathcal{A}$. Then by assumption,

$R=\beta\big{(}\\{(0,000),(2,000),(3,001)\\}\big{)}=\alpha(\\{(0,000),(0,001),(1,010)\\}).$

Note that $R$ contains vertices in three different fibres, but since the
fibres form a block system for any $\alpha\in\mathcal{A}$,
$\alpha(\\{(0,000),(0,001),(1,010)\\})$ contains two vertices in one fibre and
a third vertex in a different fibre. So these two sets cannot be equal. Hence
$\beta\notin\mathcal{A}\xi$.

Thus $\beta\in\mathcal{A}$, so $\beta=\tau\delta$ for some
$\delta\in\langle\rho,\mu\rangle$. Note that $(2,000)$ and $(3,001)$ are
adjacent, but neither is adjacent to $(0,000)$. Thus $\beta$ fixes $(0,000)$.
If the induced action of $\beta$ on the fibres fixes $\mathcal{F}_{0}$, then
either $\delta=$ id or $\delta=\mu$. Since $\mu$ does not interchange fibres
$\mathcal{F}_{2}$ and $\mathcal{F}_{3}$, $\delta=$ id. Thus $\beta$ fixes
every vertex in $R$, which contains $\\{(0,000),(3,001)\\}$, the determining
set for $\operatorname{PX}(4,3)$ found in Proposition 2. Hence
$\beta=\text{id}$. Thus this is a 2-distinguishing coloring, proving that
$\operatorname{Dist}(\operatorname{PX}(4,3))=2$.

Next we show that we cannot create a 2-distinguishing coloring with fewer red
vertices. If $R=\\{(i,x)\\}$, then $\tau_{i-1}$ is a nontrivial automorphism
preserving the coloring. To show that no two-element set of red vertices
provides a distinguishing coloring, it suffices, by vertex transitivity, to
show that every vertex in $\operatorname{PX}(4.3)$ is interchangeable with
$z=(0,000)$. Corollary 1 shows that $z=(0,000)$ is interchangeable with every
vertex in $\operatorname{PX}(4,3)$ by some $\alpha\in\mathcal{A}$ except those
listed below:

$(1,010),(1,011),(1,100),(1,101),(3,010),(3,110),(3,001),(3,101).$ (*)

For each vertex (*), we can find $\alpha\in\mathcal{A}$ such that $\alpha\xi$
interchanges it with $(0,000)$. For $(1,010)$, we seek $\alpha\in\mathcal{A}$
that satisfies $\alpha(\xi\cdot(0,000))=(1,010)$ and
$\alpha(\xi\cdot(1,010))=(0,000)$. Referring to Table 2 for the action of
$\xi$, we seek $\alpha\in\mathcal{A}$ such that $\alpha\cdot(0,000)=(1,010)$
and $\alpha\cdot(3,001))=(0,000)$. It is easy to verify that
$\alpha=\tau_{2}\rho$ satisfies this condition. For each vertex $v$ in (*),
Table 3 gives an $\alpha$ satisfying
$\alpha\xi\cdot(0,000)=\alpha\cdot(0,000)=v$ and $\alpha\xi\cdot v=(0,000)$. ∎

$v$ | $\xi\cdot v$ | $\alpha$ | $v$ | $\xi\cdot v$ | $\alpha$
---|---|---|---|---|---
$(1,010)$ | $(3,001)$ | $\tau_{2}\rho$ | $(3,010)$ | $(3,101)$ | $\tau_{0}\tau_{2}\mu_{1}$
$(1,011)$ | $(1,100)$ | $\tau_{2}\tau_{3}\mu_{3}$ | $(3,110)$ | $(1,101)$ | $\tau_{0}\tau_{2}\tau_{3}\rho^{3}$
$(1,100)$ | $(1,011)$ | $\tau_{0}\tau_{1}\mu_{3}$ | $(3,001)$ | $(1,010)$ | $\tau_{1}\rho^{3}$
$(1,101)$ | $(3,110)$ | $\tau_{0}\tau_{1}\tau_{3}\rho$ | $(3,101)$ | $(3,010)$ | $\tau_{1}\tau_{3}\mu_{1}$
Table 3: $\alpha\in\mathcal{A}$ such that $\alpha\xi$ interchanges $(0,000)$
and $v$ in $(*)$.

######  Theorem 9.

Let $n\geq 5$ and $k\geq 2$. Then
$\operatorname{Dist}(\operatorname{PX}(n,k))=2$ and
$\lceil\frac{n}{k}\rceil\leq\rho(\operatorname{PX}(n,k))\leq\lceil\frac{n}{k}\rceil+1$.

###### Proof.

Let $x=00\cdots 0,y=11\cdots 1\in\mathbb{Z}_{2}^{k}$. Then let

$R=\big{\\{}(ik,x):i\in\\{0,1,\dots,\lceil\tfrac{n}{k}\rceil-1\\}\big{\\}}\cup\big{\\{}(1,y)\big{\\}}.$

Color the vertices in $R$ red and all other vertices blue. Assume
$\alpha=\tau\delta\in\operatorname{Aut}(\operatorname{PX}(n,k))$ preserves
these color classes. Then the induced action of $\delta$ on the fibres must
preserve the set
$I=\\{0,1,k,2k,\dots,(\lceil\tfrac{n}{k}\rceil-1)k\\}\subset\mathbb{Z}_{n}$.
Note that $|R|=|I|=\lceil\tfrac{n}{k}\rceil+1<n$. Interpreting
$\mathbb{Z}_{n}$ as the vertex set of the cycle $C_{n}$, the (non-spanning)
subgraph of $C_{n}$ induced by $I$ consists of a path containing at least the
vertices $0$ and $1$, and possibly some isolated vertices. Let
$F\subset\mathbb{Z}_{n}$ denote the set of vertices in the path; these will be
the indices corresponding to a set of adjacent fibres of
$\operatorname{PX}(n,k)$ containing red vertices. Note that the action of
$\delta$ on $C_{n}$ must preserve $F$. Since no nontrivial rotation preserves
a proper subpath of $C_{n}$, $\delta\neq\rho^{s}$ for any $0\neq
s\in\mathbb{Z}_{n}$. So assume $\delta=\mu_{s}$ for some $s\in\mathbb{Z}_{n}$,
and as usual, $\tau=\tau_{0}^{u_{o}}\cdots\tau_{n-1}^{u_{n-1}}$.

First assume $k=2$. If $n\geq 5$ is odd, then $I=\\{0,1,2,4,\dots,n-1\\}$ and
$F=\\{n-1,0,1,2\\}$. For $F$ to be preserved under reflection, $\mu_{s}$ must
interchange the vertex pairs $\\{0,1\\}$ and $\\{n-1,2\\}$ in $C_{n}$. By
Lemma 1, $s=2$. In $\operatorname{PX}(n,2)$, $\alpha=\tau\mu_{2}$ must
interchange the vertex pairs $\\{(0,00),(1,11)\\}$ and
$\\{(n-1,00),(2,00)\\}$. Thus $\tau\cdot(0,11)=(0,00)$ and
$\tau\cdot(1,11)=(1,00)$, which implies $u_{0}=u_{1}=u_{2}=1$. However, it
must also be the case that $\tau\cdot(n-1,00)=(n-1,00)$, so $u_{0}=0$, a
contradiction.

If instead $n\geq 5$ is even, then $I=\\{0,1,2,4,\dots,n-2\\}$ and
$F=\\{0,1,2\\}$. In this case, $\mu_{s}$ must fix $1$ and interchange $0$ and
$2$, so by Lemma 1, $s=3$. In this case, as an element of
$\operatorname{Aut}(\operatorname{PX}(n,2))$, $\mu_{3}$ is a nontrivial
automorphism preserving $R$, so this does not define a $2$-distinguishing
coloring. However, let

$R^{\prime}=\\{(0,y)\\}\cup\big{\\{}(ik,x):i\in\\{1,\dots,\lceil\tfrac{n}{k}\rceil-1\\}\big{\\}}\cup\big{\\{}(1,x)\big{\\}}.$

Then $I^{\prime}=I=\\{0,1,2,4,\dots,n-2\\}$ and $F^{\prime}=F=\\{0,1,2\\}$.
The only reflection preserving $F^{\prime}$ is still $\mu_{3}$. If
$\alpha=\tau\mu_{3}$ preserves $R^{\prime}$, then
$\tau\mu_{3}\cdot(0,11)=\tau\cdot(2,11)=(2,00)$, which means $u_{2}=u_{3}=1$.
Also, $\tau\mu_{3}\cdot(2,00)=\tau\cdot(0,00)=(0,11)$, so $u_{0}=u_{1}=1$.
This creates a contradiction because
$\tau\mu_{3}\cdot(1,00)=\tau(1,00)=(1,00)$, which implies $u_{1}=u_{2}=0$.

Now assume $k>2$. If $n\neq 1\bmod k$, then $F=\\{0,1\\}$. Then $\mu_{s}$ must
interchange $0$ and $1$, so by Lemma 1, $s=k$. Since $\alpha=\tau\mu_{k}$
preserves $R$, $\tau\cdot(0,y)=(0,x)$ and $\tau\cdot(1,x)=(1,y)$. Then
$u_{0}=u_{1}=\cdots=u_{k}=1$. Since $k\in I$ and $\mu_{k}$ preserves $I$,
$\mu_{k}(j)=k$ for some $j\in I\setminus\\{0,1\\}$. Then
$\alpha(j,x)=\tau\mu_{s}(j,x)=\tau\cdot(k,x)=(k,x)$, so $u_{k}=0$, a
contradiction.

If instead $n=1\bmod k$, then $F=\\{n-1,0,1\\}$. Then $\mu_{s}$ fixes $0$ and
interchanges $n-1$ and $1$, so $s=k-1$. Then $\tau\cdot(n-1,y)=(n-1,x)$ and
$\tau\cdot(1,x)=(1,y)$. Hence $u_{n-1}=u_{0}=\cdots=u_{k}=1$. However,
$\tau\cdot(0,x)=(0,x)$, so $u_{0}=u_{1}=\cdots=u_{k-1}=0$, a contradiction.

Thus $\delta\neq\mu_{s}$ for any $s\in\mathbb{Z}_{n}$, so $\delta=\text{id}$
and hence $\alpha=\tau\in K$. For every $0\leq
t\leq\lceil{\frac{n}{k}}\rceil-1$, $\mathcal{F}_{tk}$ contains exactly one red
vertex that is fixed by $\tau$, so by Lemma 2,
$u_{tk}=u_{tk+1}=\dots=u_{tk+k-1}=0$. Hence $u_{0}=\dots=u_{n-1}=0$ and so
$\tau=\text{id}$. Thus, this is a $2$-distinguishing coloring of
$\operatorname{PX}(n,k)$ with a color class of size
$\lceil\frac{n}{k}\rceil+1$, so
$\operatorname{Dist}(\operatorname{PX}(n,k))=2$ and
$\rho(\operatorname{PX}(n,k))\leq\lceil\tfrac{n}{k}\rceil+1$.

To establish the lower bound on cost, assume there exists a set of vertices
$R=\\{u_{1},u_{2},\dots,u_{r}\\}$ with $r<\lceil\frac{n}{k}\rceil$ such that
coloring the vertices of $R$ red and all other vertices blue defines a
$2$-distinguishing coloring of $\operatorname{PX}(n,k)$. If
$\alpha\in\operatorname{Aut}(\operatorname{PX}(n,k))$ fixes every vertex in
$R$, then certainly $\alpha$ preserves the color classes and so by assumption
$\alpha=\text{id}$. Hence, $R$ is a determining set of size
$r<\lceil\frac{n}{k}\rceil$, a contradiction of Theorem 6. Thus,
$\rho(\operatorname{PX}(n,k))\geq\lceil\tfrac{n}{k}\rceil$. ∎

Figure 4: $\operatorname{PX}(13,4)$ with a $2$-distinguishing coloring of cost
$5=\lceil\tfrac{13}{4}\rceil+1$.

The remaining theorems indicate which Praeger-Xu graphs (for $n\geq 5$ and
$k\geq 2$) have cost $\lceil\frac{n}{k}\rceil$ and which have cost
$\lceil\frac{n}{k}\rceil+1$.

######  Theorem 10.

Let $n\geq 5$ and $2\leq k<n$. If $k$ divides $n$, then
$\rho(\operatorname{PX}(n,k))=\lceil\frac{n}{k}\rceil+1=\frac{n}{k}+1$.

###### Proof.

Let $R\subset V$ be any set of $\frac{n}{k}$ vertices. Color every vertex in
$R$ red and every other vertex blue. It suffices to show we can always find a
nontrivial automorphism preserving $R$.

Let $I=\\{i_{1},i_{2},\dots,i_{r}\\}\subseteq\mathbb{Z}_{n}$ be the set of
indices of fibres containing red vertices, where we assume that as integers,
$0\leq i_{1}<i_{2}<\dots<i_{r}<n$. Then the gaps between these fibres contain
$i_{2}-i_{1}-1,i_{3}-i_{2}-1,\dots,n+i_{1}-i_{r}-1$ fibres, respectively. If
there exists $i_{p}\in I$ such that the gap between $i_{p}$ and $i_{p+1}$
contains at least $k$ fibres, then $\tau_{i_{p+1}-1}$ is a nontrivial
automorphism that preserves colors. So assume that for all $i_{p}\in I$, the
gap between $i_{p}$ and $i_{p+1}$ contains fewer than $k$ fibres.

Suppose there exists $i_{p}\in I$ such that the gap between $i_{p}$ and
$i_{p+1}$ contains fewer than $k-1$ fibres. Since $r=|I|\leq|R|=\frac{n}{k}$,
the total number of fibres is strictly less than $r+(k-1)r=kr\leq
k\cdot\frac{n}{k}=n$, a contradiction. Thus for all $i\in\mathbb{Z}_{n}$,
$i\in I$ if and only if $i+k\in I$, so the induced action of $\rho^{k}$
preserves $I$ as a subset of $V(C_{n})$.

Since the fibres containing red vertices are separated by $k-1$ fibres, we can
define $\tau\in K$ such that $\tau$ adjusts the bitstring components of
vertices in these fibres independently. More precisely, let
$\tau=\tau_{0}^{u_{0}}\tau_{1}^{u_{1}}\cdots\tau_{n-1}^{u_{n-1}}$, where
$u_{m}=1$ if and only if there exist $(i_{p},x),(i_{p+1},y)\in R$ such that
$x_{m-i_{p}}\neq y_{m-i_{p+1}}$. Then for all $(i_{p},x)\in R$,
$\tau\rho^{k}\cdot(i_{p},x))=\tau\cdot(i_{p+1},x)=(i_{p+1},y)\in R.$ Thus,
$\tau\rho^{k}$ is a nontrivial automorphism that preserves colors. ∎

######  Theorem 11.

If $5\leq n<2k$, then $\rho(\operatorname{PX}(n,k))=\lceil\frac{n}{k}\rceil=2$
.

###### Proof.

Let $j=\lfloor\tfrac{n}{2}\rfloor-1$. Then $5\leq n<2k$ implies $0<j<k-1$.
Next, let $R=\\{z,v\\}$ where $z=(0,000\cdots 0)$ and $v=(j,y)=(j,011\cdots
1))$. Color vertices in $R$ red and all other vertices blue; assume
$\alpha\in\operatorname{Aut}(\operatorname{PX}(n,k))$ preserves these color
classes. Let
$M=\big{\\{}0,1,\dots,k-1\big{\\}}\cap\big{\\{}j,j+1,\dots,j+k-1\big{\\}}.$
Since $0<j<k-1$, $j\in M$. For $m=j$, $y_{m-j}=y_{0}=0$, but
$y_{k-1-m}=y_{k-1-j}=1.$ By Corollary 1, $z$ and $v$ are not interchangeable,
so $\alpha$ can only preserve $R$ by fixing $z$ and $v$. Because fibres
$\mathcal{F}_{0}$ and $\mathcal{F}_{j}$ are not antipodal, $R$ is a
determining set by Theorem 5. By definition, $\alpha$ is the identity. Thus we
have defined a $2$-distinguishing coloring in which the smaller color class
has size $2$. ∎

######  Theorem 12.

Let $k\geq 2$ and $n>2k$ such that $k$ does not divide $n$. Then

$\rho(\operatorname{PX}(n,k))=\begin{cases}\lceil\tfrac{n}{k}\rceil+1,&\text{if
}n=-1\bmod k,\\\ \lceil\tfrac{n}{k}\rceil,\quad&\text{if }n\neq-1\bmod
k.\end{cases}$

###### Proof.

First assume $n=-1\bmod k$, so $n=\lceil\frac{n}{k}\rceil k-1$. Let $R$ be any
set of $\lceil\frac{n}{k}\rceil$ vertices. Color every vertex in $R$ red and
every other vertex blue. Let
$I=\\{i_{1},i_{2},\dots,i_{r}\\}\subset\mathbb{Z}_{n}$ be the set of indices
of the fibres containing red vertices, where as integers, $0\leq
i_{1}<i_{2}<\cdots<i_{r}<n$. We will show that there is a nontrivial
automorphism preserving $R$.

If there exists $i_{p}\in I$ such that the gap between $i_{p}$ and $i_{p+1}$
contains at least $k$ fibres, then $\tau_{i_{p}+k}$ is a nontrivial
automorphism that preserves colors. So assume that every gap has at most $k-1$
fibres. Suppose there exist at least two gaps that contain at most $k-2$
fibres. Then the total number of fibres is at most

$r+2(k-2)+(r-2)(k-1)=rk-2\leq\lceil\tfrac{n}{k}\rceil
k-2<\lceil\tfrac{n}{k}\rceil k-1=n,$

a contradiction. Thus at most one gap contains at most $k-2$ fibres and the
others contain exactly $k-1$ fibres. If two vertices $u,v\in R$ are in the
same fibre, then $r<\lceil\frac{n}{k}\rceil$ and then the total number of
fibres is

$r+(r-1)(k-1)+k-2=rk-1<\lceil\tfrac{n}{k}\rceil k-1=n,$

a contradiction. Thus $r=\lceil\frac{n}{k}\rceil$, every gap except one
contains $k-1$ fibres, and the remaining gap contains $k-2$ fibres. By vertex-
transitivity, we can assume
$I=\\{0,k,2k,\dots,(\lceil\tfrac{n}{k}\rceil-1)k\\}$.

Let $j=(\lceil\tfrac{n}{k}\rceil-1)k=n-(k-1)$. The gap between
$\mathcal{F}_{j}$ and $\mathcal{F}_{0}$ is the one containing exactly $k-2$
fibres; all other gaps contain $k-1$ fibres. Let $u=(0,x),v=(j,y)\in R$ be the
red vertices in $\mathcal{F}_{0}$ and $\mathcal{F}_{j}$, respectively. Then,
as defined in Lemma 3, let

$M=\big{\\{}0,1,\dots,k-1\big{\\}}\cap\big{\\{}j,j+1,\dots,j+k-1\\}=\big{\\{}0\big{\\}}.$

For the only $m\in M$, $m-j=k-1$ and $m-i=0.$ Then $(x^{-})_{m-j}=x_{0}$,
$y_{m-j}=y_{k-1}$, $(y^{-})_{m-i}=(y^{-})_{0}=y_{k-1}$, and $x_{m-i}=x_{0}$.
Of course, $x_{0}=y_{k-1}$ if and only if $y_{k-1}=x_{0}$. By Lemma 3 $u$ and
$v$ are interchangeable by an automorphism of the form by
$\alpha=\tau\mu_{s}\in\mathcal{A}$, where $s=n=0\bmod n$ and
$\tau=\tau_{0}^{u_{0}}\tau_{1}^{u_{1}}\cdots\tau_{n-1}^{u_{n-1}}$ is designed
to flip exactly the right bits of the bitstring components of vertices in
$\mathcal{F}_{0}$ and $\mathcal{F}_{j}$. More precisely, let
$t\in\\{0,1,\dots,k-1\\}$. If $y_{t}\neq(x^{-})_{t}=x_{k-1-t}$, then
$u_{j+t}=u_{k-1-t}=1$; if $y_{t}=(x^{-})_{t}=x_{k-1-t}$, then
$u_{j+t}=u_{k-1-t}=0$. Note that this prescribes the value of $u_{m}$ for all
$m\in\\{0,1,\dots k-1\\}\cup\\{j,j+1,\dots,j+k-1\\}$; vertices in
$\mathcal{F}_{0}$ and $\mathcal{F}_{j}$ are unaffected by the value $u_{\ell}$
for any $\ell\in\\{k,k+1,\dots,j-1\\}$.

We claim that we can set the value of $u_{\ell}$ for all
$\ell\in\\{k,k+1,\dots,j-1\\}$ in such a way that $\tau\mu_{0}$ preserves $R$.
Note that

$\\{k,k+1,\dots,j-1\\}=\bigsqcup_{a=1}^{\lceil\frac{n}{k}\rceil-2}\\{ak,ak+1,ak+2,\dots,ak+k-1\\}.$

Let $b\in\\{1,\dots,\lceil\frac{n}{k}\rceil-2\\}$ and let $(bk,w)$ be the red
vertex in $\mathcal{F}_{bk}$. Then
$\tau\mu_{n}\cdot(bk,w)=\tau\cdot(ak,w^{-})$, for some
$a\in\\{1,\dots,\lceil\frac{n}{k}\rceil-2\\}\setminus\\{b\\}$. We can arrange
to have $\tau(ak,w^{-})$ equal the red vertex in $\mathcal{F}_{ak}$ by
flipping bits in $w^{-}$ as necessary; this can be achieved by appropriately
setting the values of $u_{ak},u_{ak+1},\dots,u_{ak+k-1}$. These values won’t
affect vertices in any of the other fibres containing red vertices.

Now assume $n\neq-1\bmod k$; because we are also assuming that $k\nmid n$, the
remainder after $n$ is divided by $k$ satisfies
$0<n-(\lceil\frac{n}{k}\rceil-1)k<k-1$. Again, let
$I=\\{0,k,2k,\dots,(\lceil\frac{n}{k}\rceil-1)k\\}$. To simplify notation,
again let $j=(\lceil\frac{n}{k}\rceil-1)k$. Then let

$R=\\{(i,00\cdots 00):i\in I\setminus\\{j\\}\\}\cup\\{(j,00\cdots 01)\\}.$

Note that $|R|=|I|=\lceil\frac{n}{k}\rceil$. Color every vertex in $R$ red and
all other vertices blue. Let
$\alpha=\tau\delta\in\mathcal{A}=\operatorname{Aut}(\operatorname{PX}(n,k))$
such that $\alpha$ preserves these color classes. The induced action of
$\alpha$ on the fibres must preserve the set $I$, interpreted as a subset of
$V(C_{n})$. The distance between $0$ and $j=(\lceil\frac{n}{k}\rceil-1)k$ in
$C_{n}$ is strictly less than $k+1$, whereas the distance between any other
two consecutive elements of $I$ in $C_{n}$ is exactly $k+1$. So no nontrivial
rotation preserves $I$.

Thus $\delta=\mu_{s}$, where $\mu_{s}$ interchanges $0$ and $j$. Then
$\tau\mu_{s}$ interchanges the red vertices in $\mathcal{F}_{0}$ and
$\mathcal{F}_{j}$, so $\tau\delta\cdot(0,00\cdots 0)=\tau(j,00\cdots
0)=(j,00\cdots 01)$, which implies $u_{j}=u_{j+1}=\dots=u_{j+k-2}=0$ and
$u_{j+k-1}=1$. Additionally, $\tau\delta\cdot(j,00\cdots
01)=\tau\cdot(0,10\cdots 00)=(0,00\cdots 00)$, which implies $u_{0}=1$ and
$u_{2}=u_{3}=\dots=u_{k-1}=0$. A contradiction arises because $0<n-j<k-1$
implies that in $\mathbb{Z}_{n}$, $0=n=j+m$ for some
$m\in\\{1,2,\dots,k-2\\}$. Thus, $\delta=\text{id}$ and so
$\alpha=\tau=\tau_{0}^{u_{0}}\tau_{1}^{u_{1}}\cdots\tau_{n-1}^{u_{n-1}}\in K$.

For every $0\leq t\leq\lceil{\frac{n}{k}}\rceil-1$, $\mathcal{F}_{tk}$
contains exactly one red vertex that is fixed by $\tau$, so by Lemma 2,
$u_{tk}=u_{tk+1}=\dots=u_{tk+k-1}=0$. Hence $u_{0}=\dots=u_{n-1}=0$ and so
$\tau=\text{id}$. Thus, this is a $2$-distinguishing coloring of
$\operatorname{PX}(n,k)$ of with a color class of size
$\lceil\frac{n}{k}\rceil$. By Theorem 9,
$\rho(\operatorname{PX}(n,k))=\lceil\frac{n}{k}\rceil$. ∎

Our results on distinguishing number and cost are summarized below.

######  Theorem 13.

Let $n\geq 3$ and $2\leq k<n$. Then
$\operatorname{Dist}(\operatorname{PX}(n,k))=2$ and

$\rho(\operatorname{PX}(n,k))=\begin{cases}5,\,&\text{ if }(n,k)=(4,2),\\\
\lceil\tfrac{n}{k}\rceil,&\text{ if }5\leq n<2k\text{ or }\\\ &\text{ if
}2k<n\text{ and }n\notin\\{0\bmod k,-1\bmod{k}\\},\\\
\lceil\tfrac{n}{k}\rceil+1,&\text{ otherwise.}\end{cases}$

## References

  * [1] M. O. Albertson.  Distinguishing Cartesian powers of graphs.  Electron. J. Combin., 12:17, 2005.
  * [2] M. O. Albertson and D. L. Boutin.  Using determining sets to distinguish Kneser graphs.  Electron. J. Combin., 14:R20, 2007.
  * [3] B. Bogstad and L. J. Cowen.  The distinguishing number of the hypercube.  Discrete Math., 283(1-3):29–35, 2004.
  * [4] D. Boutin, S. Cockburn, L. Keough, S. Loeb, K. Perry, and P. Rombach.  Determining number and cost of generalized Mycielskian graphs.  Discussiones Mathematicae Graph Theory, 43(1):–, 2023.
  * [5] D. L. Boutin.  Small label classes in 2-distinguishing labelings.  Ars Math. Contemp., 1(2):154–164, 2008.
  * [6] D. L. Boutin.  The determining number of a Cartesian product.  J. Graph Theory, 61(2):77–87, 2009.
  * [7] D. L. Boutin.  The cost of 2-distinguishing hypercubes.  Discrete Math., 344(9):112512, 2021.
  * [8] S. Cockburn and S. Loeb.  Symmetry parameters of two-generator circulant graphs, 2023.  arXiv:2305.15704.
  * [9] A. Gardiner and C. Prager.  A characterization of certain families of 4-valent symmetric graphs.  Europenan Journal of Combinatorics, 15(4):382–397, 1994.
  * [10] W. Imrich and S. Klavžar.  Distinguishing Cartesian powers of graphs.  J. Graph Theory, 53(3):250–260, 2006.
  * [11] R. Jajcay, P. Potočnik, and S. Wilson.  The Praeger-Xu graphs: Cycle structures, maps and semitransitive orientations.  Acta Mathematica Universitatis Comenianae, 88(2):269–291, 2019\.
  * [12] S. Klavžar and X. Zhu.  Cartesian powers of graphs can be distinguished by two labels.  European J. Combin., 28(1):303–310, 2007.
  * [13] P. Potočnik, P. Spiga, and G. Verret.  Tetravalent arc-transitive graphs with unbounded vertex-stabilizers.  Bulletin of the Australian Mathematical Society, 84:79 – 89, 2010\.
  * [14] C. E. Praeger and M.-Y. Xu.  A characterization of a class of symmetric graphs of twice prime valency.  European Journal of Combinatorics, 10(1), 1989.
  * [15] S. W. R. Jajcay, P. Potočnik.  On the Cayleyness of Praeger-Xu graphs.  Journal of Combinatorial Theory, Series B, 152, 2021.