ON THE CAYLEYNESS OF PRAEGER–XU GRAPHS

Abstract

We give a sufficient and necessary condition for a Praeger–Xu graph to be a Cayley graph.

1 Scope of this note

The Praeger–Xu graphs, introduced by Praeger and Xu in [2], have exponentially large groups of automorphisms, with respect to the number of vertices. This fact causes various complications with regard to many natural questions.

In their recent work [1], Jajcay et al. gave a sufficient and necessary condition for a Praeger–Xu graph to be a Cayley graph. Explicitly, [1, Theorem 1.1] states that, for any positive integer $n\geq 3$ , $n\ne 4$ , and for any positive integer $k\leq n-1$ , the Praeger–Xu graph $\textrm {PX}(n,k)$ is a Cayley graph if and only if one of the following holds:

1. (i) the polynomial $t^{n}+1$ has a divisor of degree $n-k$ in $\mathbb {Z}_{2}[t]$ ;

2. (ii) n is even, and there exist polynomials $f_{1},f_{2},g_{1},g_{2},u,v\in \mathbb {Z}_{2}[t]$ such that $u,v$ are palindromic of degree $n-k$ , and

   (1.1) $$ \begin{align} t^{n}+1 = f_{1}(t^{2})u(t) + tg_{1}(t^{2})v(t) = f_{2}(t^{2})v(t) + tg_{2}(t^{2})u(t). \end{align} $$

Our aim here is to prove that (ii) implies (i), thus obtaining the following refinement. (It can be verified that $\textrm {PX}(4,1)$ , $\textrm {PX}(4,2)$ and $\textrm {PX}(4,3)$ are Cayley graphs.)

Theorem 1.1. For any positive integer $n\geq 3$ and for any positive integer $k\leq n-1$ , the Praeger–Xu graph $\mathrm{PX}(n,k)$ is a Cayley graph if and only if the polynomial $t^{n}+1$ has a divisor of degree $n-k$ in $\mathbb {Z}_{2}[t]$ .

Using the factorisation of $t^{n}+1$ in $\mathbb {Z}_{2}[t]$ , we give a purely arithmetic condition for the Cayleyness of $\textrm {PX}(n,k)$ . Let $\varphi $ be the Euler $\varphi $ -function and, for every positive integer d, let

$$ \begin{align*} \omega(d):=\min \lbrace c\in \mathbb{N} \mid d \text{ divides } 2^{c}-1 \rbrace \end{align*} $$

be the multiplicative order of $2$ modulo d.

Corollary 1.2. Let a be a nonnegative integer, let b be an odd positive integer, let $n:=2^{a}b$ with $n\geq 3$ and let k be a positive integer with $k\leq n-1$ . The Praeger–Xu graph $\mathrm{PX}(n,k)$ is a Cayley graph if and only if k can be written as

(1.2) $$ \begin{align} k= \sum_{d\mid b} \alpha_{d} \omega(d),\quad \text{for some integers }\alpha_{d}\text{ with } 0\leq \alpha_{d} \leq \frac{2^{a}\varphi(d)}{\omega(d)}. \end{align} $$

2 Proof of Theorem 1.1

Suppose (ii) holds. We aim to show that $t^{n}+1$ is divisible by a polynomial of degree $n-k$ in $\mathbb {Z}_{2}[t]$ , implying (i). Working in characteristic $2$ , (1.1) can be written as

$$ \begin{align*} t^{n}+1=f_{1}^{2}(t)u(t)+tg_{1}^{2}(t)v(t)=f_{2}^{2}(t)v(t)+tg_{2}^{2}(t)u(t), \end{align*} $$

in short,

(2.1) $$ \begin{align} t^{n}+1=f_{1}^{2}u+tg_{1}^{2}v=f_{2}^{2}v+tg_{2}^{2}u. \end{align} $$

If $g_{1}=0$ or if $g_{2}=0$ , then the result follows from (2.1), and the fact that u and v have degree $n-k$ . Therefore, for the rest of the argument, we may suppose that $g_{1},g_{2}\ne 0$ . Moreover, observe that $f_{1},f_{2}\ne 0$ , because t does not divide $t^{n}+1$ .

We introduce four polynomials $u_{e},u_{o},v_{e},v_{o} \in \mathbb {Z}_{2}[t]$ such that

$$ \begin{align*} u:=u_{e}^{2}+tu_{o}^{2} , \quad v:=v_{e}^{2}+tv_{o}^{2}.\end{align*} $$

Substituting these expansions for u and v in (2.1),

$$ \begin{align*} t^{n}+1&=f_{1}^{2}u_{e}^{2}+t^{2}g_{1}^{2}v_{o}^{2}+t(f_{1}^{2}u_{o}^{2}+g_{1}^{2}v_{e}^{2}),\\[5pt] t^{n}+1&=f_{2}^{2}v_{e}^{2}+t^{2}g_{2}^{2}u_{o}^{2}+t(f_{2}^{2}v_{o}^{2}+g_{2}^{2}u_{e}^{2}). \end{align*} $$

Recall that n is even. By splitting the equations into even and odd degree terms, we obtain

$$ \begin{align*} t^{n}+1&=f_{1}^{2}u_{e}^{2}+t^{2}g_{1}^{2}v_{o}^{2}, \quad 0=t(f_{1}^{2}u_{o}^{2}+g_{1}^{2}v_{e}^{2}),\\[5pt] t^{n}+1&=f_{2}^{2}v_{e}^{2}+t^{2}g_{2}^{2}u_{o}^{2}, \quad 0=t(f_{2}^{2}v_{o}^{2}+g_{2}^{2}u_{e}^{2}). \end{align*} $$

Set $m:=n/2$ . Since we are working in characteristic $2$ ,

(2.2) $$ \begin{align} &t^{m}+1=f_{1}u_{e}+tg_{1}v_{o}, \quad t^{m}+1=f_{2}v_{e}+tg_{2}u_{o}, \end{align} $$

(2.3) $$ \begin{align} &\hspace{-42pt}f_{1}u_{o}=g_{1}v_{e},\qquad\qquad\quad f_{2}v_{o}=g_{2}u_{e}. \end{align} $$

Since u and v are palindromic by assumption, we get $1=u(0) =u_{e}(0)$ and ${1=v(0) =v_{e}(0)}$ . In particular, both $u_{e}$ and $v_{e}$ are not zero. From (2.2) and (2.3),

(2.4) $$ \begin{align} f_{1}=&\frac{t^{m}+1}{u_{e}v_{e}+tu_{o}v_{o}}v_{e}, \quad g_{1}=\frac{t^{m}+1}{u_{e}v_{e}+tu_{o}v_{o}}u_{o},\nonumber\\ f_{2}=&\frac{t^{m}+1}{u_{e}v_{e}+tu_{o}v_{o}}u_{e}, \quad g_{2}=\frac{t^{m}+1}{u_{e}v_{e}+tu_{o}v_{o}}v_{o}. \end{align} $$

Our candidate for the desired divisor of $t^{n} + 1$ is $s:=u_{e}v_{e}+tu_{o}v_{o}$ . Let us show first that $\deg (s)=n - k$ . Since $u_{e}v_{e}$ and $u_{o}v_{o}$ have even degree, we deduce

$$ \begin{align*}\deg(s) = \max \{\deg(u_{e}v_{e}), \deg(tu_{o}v_{o})\}.\end{align*} $$

Recall $u=u_{e}^{2}+tu_{o}^{2}$ and $v=v_{e}^{2}+tv_{o}^{2}$ . If $n-k$ is even, then

$$ \begin{align*} \deg(u_{e})=\deg(v_{e})=\frac{n - k}{2} \quad\textrm{and}\quad \deg(u_{o}),\deg(v_{o})< \frac{n-k-1}{2}. \end{align*} $$

However, if $n-k$ is odd, then

$$ \begin{align*} \deg(u_{e}),\deg(v_{e})<\frac{n-k}{2} \quad\textrm{and}\quad \deg(u_{o})=\deg(v_{o}) = \frac{n-k-1}{2}. \end{align*} $$

Therefore, in both cases, $\deg (s) = n-k$ .

It remains to prove that s divides $t^{n}+1$ . Since $f_{1},g_{1},f_{2},g_{2}$ are polynomials, by (2.4), s divides

$$ \begin{align*} \gcd((t^{m}+1)v_{e},(t^{m}+1)v_{o},(t^{m}+1)u_{e},(t^{m}+1)u_{o})=(t^{m}+1)\gcd(v_{e},v_{o},u_{e},u_{o}). \end{align*} $$

Observe that $\gcd (v_{e},v_{o},u_{e},u_{o})$ divides $f_{1}u_{e}+tg_{1}v_{o}$ , and hence, in view of the first equation in (2.2), $\gcd (v_{e},v_{o},u_{e},u_{o})$ divides $t^{m}+1$ . Therefore, s divides ${(t^{m}+1)^{2}=t^{n}+1}$ .

3 Proof of Corollary 1.2

By Theorem 1.1, deciding if a Praeger–Xu graph $\textrm {PX}(n,k)$ is a Cayley graph is tantamount to deciding if $t^{n}+1$ admits a divisor of order k in $\mathbb {Z}_{2}[t]$ . An immediate way to proceed is to study how $t^{n}+1$ can be factorised in irreducible polynomials.

Let $n=2^{a}b$ , with $\gcd (2,b)=1$ . Since we are in characteristic $2$ ,

$$ \begin{align*} t^{n}+1 = t^{2^{a}b}+1 = (t^{b}+1)^{2^{a}}. \end{align*} $$

Furthermore, if $\lambda _{d}(t)\in \mathbb {Z}[t]$ denotes the dth cyclotomic polynomial, then

$$ \begin{align*} t^{b}+1 = \prod_{d|b} \lambda_{d}(t) \end{align*} $$

is the factorisation of $t^{b}+1$ in irreducible polynomials over $\mathbb {Q}[t]$ , by Gauss’ theorem. Since the Galois group of any field extension of $\mathbb {Z}_{2}$ is a cyclic group generated by the Frobenius automorphism, the degree of an irreducible factor of $\lambda _{d}(t)$ in $\mathbb {Z}_{2}[t]$ is the smallest c such that a dth primitive root $\zeta $ raised to the power $2^{c}$ is $\zeta $ , that is, $\omega (d)$ . Hence, $\lambda _{d}(t)$ in $\mathbb {Z}_{2}[t]$ factorises into $\varphi (d)/\omega (d)$ irreducible polynomials, each having degree $\omega (d)$ .

Therefore, $t^{n}+1\in \mathbb {Z}_{2}[t]$ has a divisor of degree k if and only if k can be written as the sum of some $\omega (d)$ terms, each summand repeated at most $2^{a}\varphi (d)/\omega (d)$ times, which is exactly (1.2).