###### Abstract

Let $G$ be a graph of even order and let $K_{G}$ be the complete graph on the
same vertex set of $G$. A pairing of a graph $G$ is a perfect matching of the
graph $K_{G}$. A graph $G$ has the Pairing-Hamiltonian property (for short,
the PH-property) if for each one of its pairings, there exists a perfect
matching of $G$ such that the union of the two gives rise to a Hamiltonian
cycle of $K_{G}$. In 2015, Alahmadi _et al._ gave a complete characterisation
of the cubic graphs having the PH-property. Most naturally, the next step is
to characterise the quartic graphs that have the PH-property. In this work we
propose a class of quartic graphs on two parameters, $n$ and $k$, which we
call the class of accordion graphs $A[n,k]$. We show that an infinite family
of quartic graphs (which are also circulant) that Alahmadi _et al._ stated to
have the PH-property are, in fact, members of this general class of accordion
graphs. We also study the PH-property of this class of accordion graphs, at
times considering the pairings of $G$ which are also perfect matchings of $G$.
Furthermore, there is a close relationship between accordion graphs and the
Cartesian product of two cycles. Motivated by a recent work by Bogdanowicz
(2015), we give a complete characterisation of those accordion graphs that are
circulant graphs. In fact, we show that $A[n,k]$ is not circulant if and only
if both $n$ and $k$ are even, such that $k\geq 4$.

###### keywords:

Hamiltonian cycle, perfect matching, quartic graph, circulant graph.

counter-format=(tsk[r]), label-width=4ex

Accordion graphs: Hamiltonicity, matchings and isomorphism with quartic
circulantsDedicated to Professor Anton Buhagiar (1954–2020) — a brilliant
mathematician, a passionate musician, a dedicated teacher, a cheerful friend.

John Baptist Gauci Department of Mathematics, University of Malta, Malta john-
<EMAIL_ADDRESS>
Jean Paul Zerafa Dipartimento di Scienze Fisiche, Informatiche e Matematiche
Università degli Studi di Modena e Reggio Emilia, Italy;
Department of Technology and Entrepreneurship Education, University of Malta,
Malta;
Department of Computer Science, Faculty of Mathematics, Physics and
Informatics
Comenius University, Mlynská Dolina, 842 48 Bratislava, Slovakia
<EMAIL_ADDRESS>
05C70, 05C45, 05C60.

##  1 Introduction

The graphs considered in this paper are undirected and simple (without loops
or multiple edges). A graph $G$ having vertex set $V(G)$ of cardinality $n$
and edge set $E(G)$ has a _perfect matching_ if there is a set of exactly
$\frac{n}{2}$ edges of $G$ which have all the $n$ vertices of $G$ as
endvertices. This tacitly implies that a necessary condition for a graph to
have a perfect matching is that it has an even number of vertices. Let $k$ be
a non-negative integer. A _path_ on $k$ vertices, denoted by $P_{k}$, is a
sequence of pairwise distinct vertices $v_{1},\ldots,v_{k}$ with corresponding
edge set $\\{v_{i}v_{i+1}:i\in\\{1,\ldots,k-1\\}\\}$ (if $k>1$). For $k\geq
3$, a _cycle_ of length $k$ (or a $k$-cycle), denoted by
$C_{k}=(v_{1},\ldots,v_{k})$, is a sequence of mutually distinct vertices
$v_{1},v_{2},\ldots,v_{k}$ with corresponding edge set
$\\{v_{1}v_{2},\ldots,v_{k-1}v_{k},v_{k}v_{1}\\}$. A _Hamiltonian cycle
(path)_ of a graph $G$ is a cycle (path) in $G$ that visits all the vertices
of $G$ exactly once. We refer the reader to [5] for definitions and notation
not explicitly stated here.

The two main concepts of this paper, namely Hamiltonicity and perfect
matchings, have been extensively studied in literature by various authors and
in various settings. The study of both together has recently been put in the
limelight in [2], where the authors ask whether a perfect matching of the
complete graph $K_{G}$ on the same vertex set as a graph $G$, called a
_pairing_ of $G$, can be _extended_ to a Hamiltonian cycle of $K_{G}$ by using
only edges of $G$. Equivalently, given a pairing $M$ of $G$, we say that $M$
can be extended to a Hamiltonian cycle $H$ of $K_{G}$ if we can find another
perfect matching $N$ of $G$ such that $M\cup N=E(H)$, where $E(H)$ is the
corresponding edge set of the Hamiltonian cycle $H$. By using this
terminology, the authors of [2] define a graph $G$ on an even number of
vertices as having the _Pairing-Hamiltonian property_ (or, for short, the _PH-
property_) if every pairing $M$ of $G$ can be extended to a Hamiltonian cycle
$H$ of $K_{G}$. On a similar flavour, the authors of [1] define the _Perfect-
Matching-Hamiltonian property_ (or, for short, the _PMH-property_) for a graph
$G$ if every perfect matching of $G$ can be extended to a Hamiltonian cycle of
$K_{G}$, which in this case, would also be a Hamiltonian cycle of $G$ itself.
For simplicity, if a graph $G$ admits the PMH-property we shall say that $G$
is _PMH_. It can be easily seen that if a graph does not have the PMH-
property, then it surely does not have the PH-property, although the converse
is not true. We remark that the PMH-property was already studied in the 1970s
by Häggkvist and Las Vergnas (see [8, 11]).

A complete characterisation of the cubic graphs having the PH-property was
given in [2], and thus the most obvious next step would be to characterise
$4$-regular graphs which have the PH-property. This endeavour proved to be
more elusive, and thus far a complete characterisation of such quartic graphs
remains unknown. In an attempt to advance in this direction, in Section 2, we
define a class of graphs on two parameters, $n$ and $k$, which we call the
class of _accordion graphs_ $A[n,k]$. This class presents a natural
generalisation of the well-known antiprism graphs, and of a class of graphs
which is known to have the PH-property, corresponding to $A[n,1]$ and
$A[n,2]$, respectively. In the same section, we discuss some fundamental
properties and characteristics of accordion graphs and, in particular, we see
that accordion graphs can be drawn in a grid-like manner, which resembles a
drawing of the Cartesian product of two cycles $C_{n_{1}}\square C_{n_{2}}$,
for appropriate cycle lengths $n_{1}$ and $n_{2}$. In Section 3 we prove that
all antiprism graphs have the PMH-property but only four of them also have the
PH-property. In the same section, we provide a proof that $A[n,2]$ has the PH-
property, which result, although known to be communicated by the authors of
[2], has no published proof. These encouraging outcomes motivate our proposal
of the class of accordion graphs as a possible candidate for graphs having the
PMH-property and/or the PH-property. Empirical evidence suggests that, apart
from the above mentioned, there are (possibly an infinite number of) other
accordion graphs which have the PMH-property, and possibly some of them even
have the PH-property, but a proof for this is currently unavailable. In
Section 4, by extending an argument introduced in [7], we show that we can
exclude some graphs $A[n,k]$ from this search for graphs having the PMH-
and/or the PH-property. In fact, we prove that the graphs $A[n,k]$ for which
the greatest common divisor of $n$ and $k$ is at least $5$ do not have the
PMH-property. The technique used does not seem to lend itself when coming to
show whether the remaining accordion graphs have, or do not have, the PH-
property or the PMH-property.

In 2015, Bogdanowicz [4] gave all possible values of $n_{1}$ and $n_{2}$ for
which the graph $C_{n_{1}}\square C_{n_{2}}$ is a circulant graph, namely when
$\gcd(n_{1},n_{2})=1$. Due to the similarity between the two classes of
graphs, in Section 5, we give a complete characterisation of which accordion
graphs are circulant graphs. We finally pose some related questions and open
problems in Section 6.

##  2 Accordion graphs

In the sequel, operations (including addition and subtraction) in the indices
of the vertices $u_{i}$ and $v_{i}$ in an accordion graph (as in the following
definition) are taken modulo $n$, with complete residue system
$[n]=\\{1,\ldots,n\\}$. For simplicity, and unless there is room for
confusion, we shall omit writing $\pmod{n}$ when referring to the indices of
$u_{i}$ and $v_{i}$.

######  Definition 2.1.

Let $n$ and $k$ be integers such that $n\geq 3$ and $0<k\leq\frac{n}{2}$. The
_accordion graph_ $A[n,k]$ is the quartic graph with vertices
$\\{u_{1},u_{2},\ldots,u_{n},v_{1},v_{2},\ldots,v_{n}\\}$ such that the edge
set consists of the edges

$\\{u_{i}u_{i+1},v_{i}v_{i+1},u_{i}v_{i},u_{i}v_{i+k}:i\in[n]\\}.$

The edges $u_{i}u_{i+1}$ and $v_{i}v_{i+1}$ are called the _outer-cycle edges_
and the _inner-cycle edges_ , respectively, or simply the _cycle edges_ ,
collectively; and the edges $u_{i}v_{i}$ and $u_{i}v_{i+k}$ are called the
_vertical spokes_ and the _diagonal spokes_ , respectively, or simply the
_spokes_ , collectively. For simplicity, we sometimes refer to the accordion
graph $A[n,k]$ as the accordion $A[n,k]$.

Figure 1: The accordion graph $A[10,3]$

An observation that will prove to be useful in the sequel revolves around the
greatest common divisor of $n$ and $k$, denoted by $\gcd(n,k)$. However,
before proceeding further, we give the definition of the Cartesian product of
graphs. The _Cartesian product_ $G\square H$ of two graphs $G$ and $H$ is a
graph whose vertex set is the Cartesian product $V(G)\times V(H)$ of $V(G)$
and $V(H)$. Two vertices $(u_{i},v_{j})$ and $(u_{k},v_{l})$ are adjacent
precisely if $u_{i}=u_{k}$ and $v_{j}v_{l}\in E(H)$ or $u_{i}u_{k}\in E(G)$
and $v_{j}=v_{l}$.

######  Remark 2.2.

The graph obtained from $A[n,k]$ by deleting the edges

$\\{u_{tq}u_{tq+1},v_{tq}v_{tq+1}:q=\gcd(n,k)\textrm{ and
}t\in\\{1,\ldots,\tfrac{n}{q}\\}\\}$

is isomorphic to the Cartesian product $C_{\frac{2n}{q}}\square P_{q}$. This
can be easily deduced by an appropriate drawing of $A[n,k]$, as shown in
Figure 2 for the case when $k=5$ and $\gcd(n,k)=5$. Thus, any perfect matching
of $C_{\frac{2n}{q}}\square P_{q}$ is also a perfect matching of $A[n,k]$,
although the converse is trivially not true.

Figure 2: Two different drawings of $A[n,k]$ when $k=5$ and $\gcd(n,k)=5$

##  3 The accordion graph $A[n,k]$ when $k\leq 2$

###  3.1 $A[n,1]$

As already mentioned above, the accordion graph $A[n,1]$ is isomorphic to the
widely known antiprism graph $A_{n}$ on $2n$ vertices. Let $M$ be a perfect
matching of $A_{n}$. We note that, if $M$ contains at least one vertical
spoke, then no diagonal spoke can be contained in $M$, and if any inner-cycle
edges are in $M$, then the outer-cycle edges having the same indices must also
belong to $M$. A similar argument can be made if $M$ contains diagonal spokes.
Thus, for every $i,j\in[n]$, $u_{i}v_{i}\in M$ or
$\\{u_{i}u_{i+1},v_{i}v_{i+1}\\}\subset M$ if and only if $u_{j}v_{j+1}\not\in
M$ or $\\{u_{j}u_{j+1},v_{j+1}v_{j+2}\\}\not\subset M$. This can be summarised
in the following remark.

######  Remark 3.1.

Let $M$ be a perfect matching of $A_{n}$. Then, $M$ is either a perfect
matching of $A_{n}-\\{u_{i}v_{i}:i\in[n]\\}$ or of
$A_{n}-\\{u_{i}v_{i+1}:i\in[n]\\}$.

Consequently, in what follows, without loss of generality, we only consider
perfect matchings of $A_{n}$ containing spokes of the type $u_{i}v_{i}$, that
is, vertical spokes, and if a perfect matching contains the edge
$u_{j}u_{j+1}$, then it must also contain the edge $v_{j}v_{j+1}$.

######  Theorem 3.2.

The antiprism $A_{n}$ has the PMH-property.

######  Proof 3.3.

Let $M$ be a perfect matching of $A_{n}$. Consider first the case when
$M=\\{u_{i}v_{i}:i\in[n]\\}$. It is easy to see that
$(v_{1},u_{1},v_{2},u_{2},\ldots,v_{n-1},u_{n-1},v_{n},u_{n})$ is a
Hamiltonian cycle of $A_{n}$ containing $M$. So assume that $M$ does not
consist of only vertical spokes. Without loss of generality, we can assume
that $M$ contains the edges $u_{n}u_{n+1}$ and $v_{n}v_{n+1}$, by Remark 3.1.
We proceed by induction on $n$. The antiprism $A_{3}$ was already shown to be
PMH in [1], since $A_{3}$ is the line graph of the complete graph $K_{4}$. So
assume result is true up to $n\geq 3$, and consider $A_{n+1}$ and a perfect
matching $M$ of $A_{n+1}$. Let $M^{\prime}$ be
$M\cup\\{u_{n}v_{n}\\}-\\{u_{n}u_{n+1},v_{n}v_{n+1}\\}$. Then, $M^{\prime}$ is
a perfect matching of $A_{n}$, and so, by the inductive step, there exists a
Hamiltonian cycle $H^{\prime}$ of $A_{n}$ which contains $M^{\prime}$. We next
show that $H^{\prime}$ can be extended to a Hamiltonian cycle $H$ of $A_{n+1}$
containing $M$ by considering each of the following possible induced paths in
$H^{\prime}$ and replacing them as indicated hereunder:

  1. (i)

$u_{n-1},u_{n},v_{n},v_{n-1}$ is replaced by
$u_{n-1},u_{n},u_{n+1},v_{n+1},v_{n},v_{n-1}$ (similarly
$u_{1},u_{n},v_{n},v_{1}$ is replaced by
$u_{1},u_{n+1},u_{n},v_{n},v_{n+1},v_{1}$);

  2. (ii)

$u_{n-1},v_{n},u_{n},u_{1}$ is replaced by
$u_{n-1},v_{n},v_{n+1},u_{n},u_{n+1},u_{1}$ (similarly
$v_{n-1},v_{n},u_{n},v_{1}$ is replaced by
$v_{n-1},v_{n},v_{n+1},u_{n},u_{n+1},v_{1}$); and

  3. (iii)

$u_{n-1},u_{n},v_{n},v_{1}$ or $u_{n-1},v_{n},u_{n},v_{1}$ are replaced by
$u_{n-1},v_{n},v_{n+1},u_{n},u_{n+1},v_{1}$ (similarly
$v_{n-1},v_{n},u_{n},u_{1}$ is replaced by
$v_{n-1},v_{n},v_{n+1},u_{n},u_{n+1},u_{1}$).

Consequently, $A_{n+1}$ has the PMH-property, proving our theorem.

######  Theorem 3.4.

The only antiprisms having the PH-property are $A_{3},A_{4},A_{5}$ and
$A_{6}$.

######  Proof 3.5.

The graph $A_{3}$ is PMH as already explained in Theorem 3.2, so what is left
to show is that every pairing $M$ of $A_{3}$ containing some edge belonging to
$E(K_{A_{3}})-E(A_{3})$ (referred to as a non-edge) can be extended to a
Hamiltonian cycle of $K_{A_{3}}$. The pairing $M$ can only contain one or
three non-edges. When $M$ consists of three non-edges then
$M=\\{u_{1}v_{3},u_{2}v_{1},u_{3}v_{2}\\}$ and this can be extended to a
Hamiltonian circuit of $K_{A_{3}}$ as follows:
$(u_{1},v_{3},u_{3},v_{2},u_{2},v_{1})$. Otherwise, assume that the only non-
edge in $M$ is $u_{1}v_{3}$, without loss of generality. Then, $M$ is either
equal to $\\{u_{1}v_{3},u_{2}v_{2},u_{3}v_{1}\\}$ or
$\\{u_{1}v_{3},u_{2}u_{3},v_{1}v_{2}\\}$, which can be extended to
$(u_{1},v_{3},u_{3},v_{1},v_{2},u_{2})$ or
$(u_{1},v_{3},u_{3},u_{2},v_{2},v_{1})$, respectively.

The graph $A_{4}$ has the PH-property because it contains the hypercube
$\mathcal{Q}_{3}$ as a spanning subgraph, and by the main theorem in [6], all
hypercubes have the PH-property .

An exhaustive computer check was conducted through Wolfram Mathematica to
verify that all pairings of the antiprism graphs $A_{5}$ and $A_{6}$ can be
extended to a Hamiltonian cycle of the same graphs, thus proving (by brute-
force) that they both have the PH-property.

Figure 3: A pairing in $A_{n}$, $n\geq 7$, which is not extendable to a
Hamiltonian cycle of $K_{A_{n}}$

The antiprism $A_{7}$ does not have the PH-property because the pairing
$M=\\{u_{1}v_{5},u_{2}v_{2},\linebreak
u_{3}v_{3},u_{4}v_{4},u_{5}v_{6},u_{6}v_{7},u_{7}v_{1}\\}$, depicted in Figure
3, cannot be extended to a Hamiltonian cycle of $K_{A_{7}}$. For, suppose not.
Let $N$ be a perfect matching of $A_{7}$ such that $M\cup N$ gives a
Hamiltonian cycle of $K_{A_{7}}$. Then,
$|N\cap\\{u_{2}u_{3},u_{2}v_{3},v_{2}v_{3}\\}|$, and
$|N\cap\\{u_{3}u_{4},u_{3}v_{4},v_{3}v_{4}\\}|$ must both be equal to $1$.
Consequently, $M\cup N$ induces a $M$-alternating path containing the edges
$\\{u_{2}v_{2},u_{3}v_{3},u_{4}v_{4}\\}$ such that its endvertices are
$x\in\\{u_{2},v_{2}\\}$ and $y\in\\{u_{4},v_{4}\\}$. If $xu_{1}\in N$, then
$N\cap\\{u_{7}u_{1},u_{1}v_{1},v_{1}v_{2}\\}$ is empty, implying that $M\cup
N$ induces the $4$-cycle $(u_{6},u_{7},v_{1},v_{7})$, a contradiction.
Therefore, $N$ contains the edge $v_{2}v_{1}$ implying that $x=v_{2}$.
Consequently, $N$ contains the edge $u_{7}u_{1}$ as well. However, this
implies that $N\cap\\{u_{6}u_{7},u_{7}v_{7},v_{7}v_{1}\\}$ is empty, implying
that $M\cup N$ induces the $4$-cycle $(u_{5},u_{6},v_{7},v_{6})$, a
contradiction once again. Thus, $A_{7}$ does not have the PH-property. The
pairing $M$ considered above can be extended to the pairing
$\\{u_{1}v_{5},u_{2}v_{2},u_{3}v_{3},u_{4}v_{4}\\}\cup\\{u_{i}v_{i+1}:i\in\\{5,\ldots,n\\}\\}$
of $A_{n}$, for any $n>7$, and by a similar argument used for $A_{7}$, we
conclude that $A_{n}$ does not have the PH-property for every $n\geq 7$.

###  3.2 $A[n,2]$

In [2], it is mentioned that Seongmin Ok and Thomas Perrett informed the
authors that they have obtained an infinite class of $4$-regular graphs having
the PH-property: such a graph in this family is obtained from a cycle of
length at least three, by replacing each vertex by two isolated vertices and
replacing each edge by the four edges joining the corresponding pairs of
vertices. More formally, the resulting graph starting from a $n$-cycle, for
$n\geq 3$, has vertex set $\\{s_{i},t_{i}:i\in[n]\\}$ such that, for every
$i\in[n]$, $s_{i}$ and $t_{i}$ are both adjacent to $s_{i+1\pmod{n}}$ and
$t_{i+1\pmod{n}}$. As far as we know, no proof of this can be found in
literature, and in what follows we give a proof of this result. Before we
proceed, we remark that the function that maps $s_{i}$ to $u_{i}$, and $t_{i}$
to $v_{i+1}$, for every $i\in[n]$, is an isomorphism between the above graph
and the accordion graph $A[n,2]$.

######  Theorem 3.6.

The accordion graph $A[n,2]$ has the PH-property, for every $n\geq 3$.

######  Proof 3.7.

Let $A^{\prime}[n,2]$ be the graph depicted in Figure 4, obtained from
$A[n,2]$ by deleting the following set of edges:
$\\{u_{1}u_{n},v_{1}v_{n},u_{n-1}v_{1},u_{n}v_{2}\\}$. We use induction on $n$
to show that $A^{\prime}[n,2]$ has the PH-property, for every $n\geq 3$. The
result then follows since $A^{\prime}[n,2]$ is a spanning subgraph of
$A[n,2]$.

Figure 4: The graph $A^{\prime}[n,2]$

When $n=3$, one can show by a case-by-case analysis (or using an exhaustive
computer search) that the graph $A^{\prime}[3,2]$ has the PH-property. So we
assume that $n>3$ and let $M$ be a pairing of $A^{\prime}[n,2]$, hereafter
denoted by $G$. If $M$ consists of only vertical spokes, that is,
$M=\\{u_{i}v_{i}:i\in[n]\\}$, then

  1. (i)

$(v_{1},u_{1},v_{3},u_{3},\ldots,v_{n-1},u_{n-1},u_{n},v_{n},u_{n-2},v_{n-2},\ldots,u_{2},v_{2})$,
when $n$ is even, or

  2. (ii)

$(v_{1},u_{1},v_{3},u_{3},\ldots,v_{n},u_{n},u_{n-1},v_{n-1},u_{n-3}\ldots,u_{2},v_{2})$,
when $n$ is odd,

is a Hamiltonian cycle of $K_{G}$ containing the pairing $M$. So assume that
$M\neq\\{u_{i}v_{i}:i\in[n]\\}$. Consequently, there exists $i\in[n]$ such
that $u_{i}v_{i}\not\in M$. Let $\alpha=\max\\{i\in[n]:u_{i}v_{i}\not\in
M\\}$. We note that by a parity argument, $\alpha>1$. Consider the two
subgraphs of $G$ induced by
$\\{u_{1},v_{1},\ldots,u_{\alpha-1},v_{\alpha-1}\\}$, denoted by $G_{1}$, and
$\\{u_{\alpha},v_{\alpha},\ldots,u_{n},v_{n}\\}$, denoted by $G_{2}$. We
remark that $G_{1}$ and $G_{2}$ are the two components obtained by deleting
from $G$ the set of edges $X$, where
$X=\\{u_{\alpha-1}u_{\alpha},v_{\alpha-1}v_{\alpha},u_{\alpha-2}v_{\alpha}\\}$
if $\alpha=n$, and
$X=\\{u_{\alpha-1}u_{\alpha},v_{\alpha-1}v_{\alpha},u_{\alpha-2}v_{\alpha},u_{\alpha-1}v_{\alpha+1}\\}$
otherwise. We also remark that depending on the value of $\alpha$, $G_{1}$ is
isomorphic to either $K_{2},C_{4}$ or $A^{\prime}[\alpha-1,2]$, and $G_{2}$ is
isomorphic to $K_{2},C_{4}$ or $A^{\prime}[n-(\alpha-1),2]$. Without loss of
generality, we assume that $|V(G_{1})|\geq|V(G_{2})|$, implying that
$3\leq\alpha\leq n$.

Next, consider the two edges $yu_{\alpha}$ and $zv_{\alpha}$ in $M$. Since for
$i>\alpha$, $u_{i}v_{i}\in M$, the vertices $y$ and $z$ both belong to
$\\{u_{1},v_{1},\ldots,u_{\alpha-1},v_{\alpha-1}\\}$. Let $M_{1}=(M\cap
E(K_{G_{1}}))\cup\\{yz\\}$. One can see that $M_{1}$ is a pairing of $G_{1}$,
and so, by the inductive step, $M_{1}$ is contained in a Hamiltonian cycle
$H_{1}$ of $K_{G_{1}}$. Consequently, $H_{1}$ contains a Hamiltonian path
$H_{1}^{\prime}$ of $K_{G_{1}}$ with endvertices $y$ and $z$.

When $\alpha=n$, by adding the edges
$yu_{\alpha},u_{\alpha}v_{\alpha},v_{\alpha}z$ to $E(H_{1}^{\prime})$, we
obtain a Hamiltonian cycle of $K_{G}$ containing $M$. For $\alpha\leq n-1$, we
proceed as follows. Let $M_{2}=(M\cap
E(G_{2}))\cup\\{u_{\alpha}v_{\alpha}\\}$. This is clearly a pairing of
$G_{2}$, and so, by the inductive step, there exists a Hamiltonian cycle
$H_{2}$ of $K_{G_{2}}$ containing $M_{2}$. Let $H_{2}^{\prime}$ be the
Hamiltonian path of $G_{2}$ obtained by deleting the edge
$u_{\alpha}v_{\alpha}$ from $E(H_{2})$. Consequently, combining
$H_{1}^{\prime}$ and $H_{2}^{\prime}$ together with the edges $yu_{\alpha}$
and $zv_{\alpha}$, we form a Hamiltonian cycle of $K_{G}$ containing $M$, as
required.

##  4 The accordion graph $A[n,k]$ when $\gcd(n,k)\geq 5$

The method adopted in this section follows a similar line of thought as that
used in [7]. Let $q=\gcd(n,k)\geq 5$, let $p=\frac{2n}{\gcd(n,k)}$ and let
$p^{\prime}=\frac{p}{2}$. Consider a grid-like drawing of the accordion graph
$A[n,k]$ as in Remark 2.2. For simplicity, we let the vertices
$v_{1},u_{1},v_{1+k},u_{1+k},\ldots,v_{1+(p^{\prime}-1)k},u_{1+(p^{\prime}-1)k}$,
be referred to as $a_{1},a_{2},\ldots,a_{p}$. We define the vertices
$\\{b_{i},c_{i},d_{i},e_{i}:i\in[p]\\}$ in a similar way, where, in
particular, the vertices $b_{1},\ldots,e_{1}$, and $b_{2},\ldots,e_{2}$,
represent $v_{2},\ldots,v_{5}$, and $u_{2},\ldots,u_{5}$, respectively. If
$\gcd(n,k)=6$, we refer to
$v_{6},u_{6},v_{6+k},u_{6+k},\ldots,v_{6+(p^{\prime}-1)k},u_{6+(p^{\prime}-1)k}$,
as $f_{1},f_{2}\ldots,f_{p}$, and if $\gcd(n,k)>6$, we simply do not label all
the other vertices since we are only interested in the subgraph of $A[n,k]$
induced by the vertices $\\{a_{i},\ldots,f_{i}:i\in[p]\\}$. This can be seen
better in Figure 5.

Figure 5: Edges belonging to $S$ in $A[n,k]$ when $\gcd(n,k)\geq 6$

For each $i\in[p]$, let $L_{i}$ and $R_{i}$ represent the edges $b_{i}c_{i}$
and $d_{i}e_{i}$, respectively, whilst $\mathcal{L}=\\{L_{i}:i\in[p]\\}$ and
$\mathcal{R}=\\{R_{i}:i\in[p]\\}$. Let $S$ denote the following set of edges:

  1. (i)

$a_{i}a_{i+1}$, for every even $i\in[p]$;

  2. (ii)

$b_{i}b_{i+1}$ and $e_{i}e_{i+1}$, for every odd $i\in[p]$;

  3. (iii)

$c_{i}d_{i}$, for every $i\in[p]$; and

  4. (iv)

in the case when $q\geq 6$, $f_{i}f_{i+1}$, for every even $i\in[p]$.

Since $p$ is even, $A[n,k]$ has a perfect matching $M$ that contains $S$.

In [7], it was shown that $C_{p}\square C_{q}$ is not PMH except when $p=q=4$.
In the case when $q\geq 6$, the proof utilises exclusively the set $S$ of
edges described above (and adapted to $C_{p}\square C_{q}$) to show that a
perfect matching $M$ containing this set cannot be extended to a Hamiltonian
cycle of $C_{p}\square C_{q}$. Since the same set $S$ of edges can also be
chosen in a perfect matching of $A[n,k]$, the proof extends naturally and
hence we have the following result.

######  Lemma 4.1.

The accordion graph $A[n,k]$ is not PMH if $\gcd(n,k)\geq 6$.

We shall now show that $A[n,k]$ is not PMH in the case when $\gcd(n,k)=5$. We
remark that, in this case, the proof in [7] cannot be extended to $A[n,k]$
because it makes use of the edges $e_{i}a_{i}$ of $C_{p}\square C_{q}$, which
are missing in $A[n,k]$. For the remaining part of this section, we shall need
some results extracted from the proof of the main theorem in [7], and adapted
for accordion graphs. We note that the arguments in [7] are quite elaborate
and lengthy, but when adapted to our case, they remain essentially the same.
Thus, in order not to risk obscuring the arguments that are really required
for this work, we omit reproducing the same detailed discussion presented in
[7], and instead give the most important points emanating from the main
theorem in the following self-contained lemma.

######  Lemma 4.2.

Let $\gcd(n,k)\geq 5$. If there exists a perfect matching $M$ of $A[n,k]$
containing $S$ and another perfect matching $N$ of $A[n,k]$ such that $M\cup
N$ is a Hamiltonian cycle $H$ of $A[n,k]$, then the following statements hold.

  1. (i)

$|\mathcal{L}\cap N|$ and $|\mathcal{R}\cap N|$ are both even and nonzero.

  2. (ii)

A maximal sequence of consecutive edges belonging to $\mathcal{L}-N$ (or
$\mathcal{R}-N$) is of even length (consecutive edges are edges having indices
which are consecutive integers taken modulo $p$, with complete residue system
$\\{1,\ldots,p\\}$).

  3. (iii)

The edges of $\mathcal{L}\cap N$ are partitioned into pairs of edges
$\\{L_{\gamma},L_{\gamma^{\prime}}\\}$, where $\gamma$ is odd and
$\gamma^{\prime}$ is the least integer greater than $\gamma$ (taken modulo
$p$) such that $L_{\gamma^{\prime}}\in N$ (and similarly for $\mathcal{R}\cap
N$). In this case, if we start tracing the Hamiltonian cycle $H$ from
$c_{\gamma}$ going towards $b_{\gamma}$, then $H$ contains a path with edges
alternating in $N$ and $M$, starting from $c_{\gamma}$ and ending at
$c_{\gamma^{\prime}}$, with the internal vertices on this path being
$\\{b_{\gamma},b_{\gamma^{\prime}}\\}$, if $\gamma^{\prime}=\gamma+1$, or
belonging to the set
$\\{b_{\gamma},a_{\gamma+1},b_{\gamma+1},\ldots,a_{\gamma^{\prime}-1},b_{\gamma^{\prime}-1},b_{\gamma^{\prime}}\\}$,
if $\gamma^{\prime}\neq\gamma+1$. In each of these two cases we refer to such
a path between $c_{\gamma}$ and $c_{\gamma^{\prime}}$ as an
$L_{\gamma}L_{\gamma^{\prime}}$_-bracket_ , or just a _left-bracket_ , with
$L_{\gamma}$ and $L_{\gamma^{\prime}}$ being the _upper_ and _lower_ edges of
the bracket, respectively. _Right-brackets_ are defined similarly.

  4. (iv)

If $L_{\gamma^{\prime}}$ is a lower edge of a left bracket, then
$L_{\gamma^{\prime}+1}$ belongs to $N$, and so is an upper edge of a possibly
different left bracket (and similarly for right-brackets).

  5. (v)

If $L_{i}\not\in N$, for some even $i\in[p]$, then $c_{i}c_{i+1}\in N$ (and
similarly for edges belonging to $\mathcal{R}-N$).

######  Lemma 4.3.

The accordion graph $A[n,k]$ is not PMH if $\gcd(n,k)=5$.

######  Proof 4.4.

Figure 6: $A[n,k]$ when $\gcd(n,k)=5$

Let $M$ be a perfect matching of $A[n,k]$ which contains the set $S$ of edges
as shown in Figure 6, and let $p=\frac{2n}{5}$ (as defined earlier on in this
section). Suppose that there exists a perfect matching $N$ of $A[n,k]$ such
that $M\cup N$ is a Hamiltonian cycle $H$ of $A[n,k]$.

Since $\mathcal{R}\cap N\neq\emptyset$, there exists some odd $\beta\in[p]$
such that $R_{\beta}\in N$. We note that the vertex $e_{\beta}$ is adjacent to
a unique $a_{\theta}$, for some odd $\theta\neq\beta$. The only way how
$a_{\theta}$ can be reached by the Hamiltonian cycle $H$ is if it is reached
by a left bracket, and so only if $a_{\theta}b_{\theta}\in N$. Consequently,
$L_{\theta}=b_{\theta}c_{\theta}$ is not in $N$, implying that
$c_{\theta}c_{\theta-1}\in N$ by Lemma 4.2. By a similar reasoning, since $H$
is a Hamiltonian cycle, $d_{\theta}d_{\theta-1}$ cannot be contained in $N$,
and so, in particular, $R_{\theta}$ and $R_{\theta-1}$ are respectively upper
and lower edges belonging to $N$. Repeating the same procedure over again,
first for $R_{\theta}$ and eventually for all edges in $\mathcal{R}$ having an
odd index, one can deduce that $\mathcal{R}\cap N=\mathcal{R}$. Since
$\mathcal{L}\cap N$ is non-empty, there exists some $\nu$ such that
$L_{\nu}\in N$. The vertex $a_{\nu}$ must be reached by some right bracket in
order to belong to $H$, however, this is impossible since $\mathcal{R}\cap
N=\mathcal{R}$, contradicting the Hamiltonicity of $H$.

By combining Lemma 4.1 and Lemma 4.3 we obtain the main result of this
section.

######  Theorem 4.5.

The accordion graph $A[n,k]$ is not PMH if $\gcd(n,k)\geq 5$.

##  5 Accordions and circulant graphs

For integers $a$ and $b$, where $1\leq a<b\leq n-1$,
$\textrm{Ci}[2n,\\{a,b\\}]$ denotes the _quartic circulant graph_ on the
vertices $\\{x_{i}:i\in[2n]\\}$, such that $x_{i}$ is adjacent to the vertices
in the set $\\{x_{i+a},x_{i-a},x_{i+b},x_{i-b}\\}$. We say that the edges
arising from these adjacencies have length $a$ and $b$, accordingly, and we
also remark that operations in the indices of the vertices $x_{i}$ are taken
modulo $2n$, with complete residue system $\\{1,\ldots,2n\\}$. In [4], the
necessary and sufficient conditions for a circulant graph to be isomorphic to
a Cartesian product of two cycles were given. Motivated by this, we show that
there is a non-empty intersection between the class of accordions $A[n,k]$ and
the class of circulant graphs $\textrm{Ci}[2n,\\{a,b\\}]$, although neither
one is contained in the other. In particular, in Theorem 5.8 we show that the
only accordion graphs $A[n,k]$ which are not circulant are those with both $n$
and $k$ even, such that $k\geq 4$. Results of a similar flavour about
$4$-regular circulant graphs, perfect matchings and Hamiltonicity can be found
in [9].

We shall be using the following two results about circulant graphs (not
necessarily quartic). Let the circulant graph on $n^{\prime}$ vertices and
with $r$ different edge lengths be denoted by
$\textrm{Ci}[n^{\prime},\\{a_{1},\ldots,a_{r}\\}]$. The first result, implied
by a classical result in number theory, says that
$\textrm{Ci}[n^{\prime},\\{a_{1},\ldots,a_{r}\\}]$ has
$\gcd(n^{\prime},a_{1},\ldots,a_{r})$ isomorphic connected components (see
[3]). Consequently, in our case we have that the circulant graph
$\textrm{Ci}[2n,\\{a,b\\}]$ is connected if and only if $\gcd(2n,a,b)=1$.
Secondly, let $\gcd(n^{\prime},a_{1},\ldots,a_{r})=1$. Heuberger [10] showed
that $\textrm{Ci}[n^{\prime},\\{a_{1},\ldots,a_{r}\\}]$ is bipartite if and
only if $a_{1},\ldots,a_{r}$ are odd and $n^{\prime}$ is even. Restated for
our purposes we have the following.

######  Corollary 5.1.

The quartic circulant graph $\textrm{Ci}[2n,\\{a,b\\}]$ is bipartite if and
only if $a$ and $b$ are both odd.

Along similar lines, we show that bipartite accordion graphs can be recognised
from the parity of their parameters $n$ and $k$, as follows.

######  Lemma 5.2.

The accordion graph $A[n,k]$ is bipartite if and only if $n$ and $k$ are both
even.

######  Proof 5.3.

When $n$ and $k$ are even, the sets
$\\{u_{1},v_{2},u_{3},v_{4},\ldots,u_{n-1},v_{n}\\}$ and
$\\{v_{1},u_{2},\linebreak v_{3},u_{4},\ldots,v_{n-1},u_{n}\\}$ are two
independent sets of vertices of $A[n,k]$, implying that for these values of
$n$ and $k$, $A[n,k]$ is bipartite. On the other hand, assume $A[n,k]$ is
bipartite. Suppose that at least one of $n$ and $k$ are odd, for
contradiction. If $n$ is odd it means that $(u_{1},u_{2},\ldots,u_{n})$ is an
odd cycle of $A[n,k]$, a contradiction. If $k$ is odd, then
$(u_{1},v_{1+k},v_{k},\ldots,v_{1})$ is an odd cycle of length $k+2$, a
contradiction as well.

Before proceeding, we recall that operations in the indices of the vertices of
$A[n,k]$ and $\textrm{Ci}[2n,\\{a,b\\}]$ are taken modulo $n$ and modulo $2n$,
respectively.

######  Lemma 5.4.

The accordion graph $A[n,2]$ is circulant for any even integer $n\geq 4$.

######  Proof 5.5.

For every even integer $n\geq 4$, we claim that the following function
$\phi:V(A[n,2])\rightarrow V(\textrm{Ci}[2n,\\{1,n-1\\}])$ defined by:

  * •

$\phi:u_{i}\mapsto x_{1+(n-1)(i-1)\pmod{2n}}$ for all $i\in[n]$,

  * •

$\phi:v_{1}\mapsto x_{2+n\pmod{2n}}$, and

  * •

$\phi:v_{i}\mapsto x_{2+(n-1)(i-1)\pmod{2n}}$ for $2\leq i\leq n$,

is an isomorphism. We first show that the function $\phi$ is bijective. Since
$n-1\geq 3$ is odd and $\gcd(n,n-1)=1$, we have that $\gcd(2n,n-1)=1$, and so
the vertices in $\\{\phi(u_{i}):1\leq i\leq n\\}$ are mutually distinct. For
the same reason, since $2+n\equiv 1+(n-1)(2n-1)\pmod{2n}$, the vertex
$\phi(v_{1})$ is distinct from any vertex $\phi(u_{i})$. Moreover, since
$1\neq n-1$ and the vertices $\phi(u_{2}),\ldots,\phi(u_{n})$ are mutually
distinct, the vertices in $\\{\phi(v_{j}):2\leq j\leq n\\}$ are mutually
distinct as well, and are not equal to some vertex $\phi(u_{i})$. Finally,
since $\gcd(n,n-1)=1$, we have that $2+(n-1)(i-1)\not\equiv 2+n\pmod{2n}$, for
any $2\leq i\leq n$. Consequently, $\phi(v_{1})$ is distinct from any vertex
$\phi(v_{j})$, proving that $\phi$ is, in fact, bijective. We next show that
$\phi$ is an isomorphism. Since $\textrm{Ci}[2n,\\{1,n-1\\}]$ has the same
number of edges as $A[n,2]$, it suffices to show that an edge in $A[n,2]$ is
mapped to an edge in $\textrm{Ci}[2n,\\{1,n-1\\}]$.

We first take an edge $u_{i}u_{j}$ from the outer-cycle of $A[n,2]$, for some
$i\in[n]$ and $j\equiv i+1\pmod{n}$, without loss of generality. Consider
$\phi(u_{i})\phi(u_{j})$. The length of $\phi(u_{i})\phi(u_{j})$ can be
calculated using $1+(n-1)(j-1)-(1+(n-1)(i-1))\pmod{2n}$. This is equal to
$n-1$, when $j\neq 1$, and to $-n^{2}+2n-1\equiv-1\pmod{2n}$, otherwise. Since
in both cases the length of the edge $\phi(u_{i})\phi(u_{j})$ belongs to
$\\{\pm 1,\pm(n-1)\\}$, $\phi(u_{i})\phi(u_{j})\in
E(\textrm{Ci}[2n,\\{1,n-1\\}])$.

Next, we consider the vertical spoke $u_{i}v_{i}$, for some $i\in[n]$. The
length of the edge $\phi(u_{i})\phi(v_{i})$ is
$2+n-(1+(n-1)(i-1))\equiv-(n-1)\pmod{2n}$, when $i=1$, and
$2+(n-1)(i-1)-(1+(n-1)(i-1))=1$, otherwise, implying that the length of the
edge $\phi(u_{i})\phi(v_{i})$ belongs to $\\{\pm 1,\pm(n-1)\\}$ in both cases.
Consequently, $\phi(u_{i})\phi(v_{i})\in E(\textrm{Ci}[2n,\\{1,n-1\\}])$.

We now take the diagonal spoke $u_{i}v_{j}$, for some $i\in[n]$, and for
$j\equiv i+2\pmod{n}$. The length of the edge $\phi(u_{i})\phi(v_{j})$ is:

  * •

$2+(n-1)(j-1)-(1+(n-1)(i-1))=2n-1\equiv-1\pmod{2n}$, when $1\leq i\leq n-2$;

  * •

$2+n-(1+(n-1)(i-1))=-n^{2}+4n-1\equiv-1\pmod{2n}$, when $i=n-1$; and

  * •

$2+(n-1)(j-1)-(1+(n-1)(i-1))=-n^{2}+3n-1\equiv n-1\pmod{2n}$, when $i=n$.

In each of these three cases, the length of $\phi(u_{i})\phi(v_{j})$ belongs
to $\\{\pm 1,\pm(n-1)\\}$, implying that $\phi(u_{i})\phi(v_{j})\in
E(\textrm{Ci}[2n,\\{1,n-1\\}])$.

Finally, we take an edge $v_{i}v_{j}$ from the inner-cycle of $A[n,2]$, for
some $i\in[n]$ and $j\equiv i+1\pmod{n}$, without loss of generality. The
length of the edge $\phi(v_{i})\phi(v_{j})$ is:

  * •

$2+n-(2+(n-1)(i-1))=-n^{2}+3n-1\equiv n-1\pmod{2n}$, when $j=1$;

  * •

$2+(n-1)(j-1)-(2+n)=-1$, when $j=2$; and

  * •

$2+(n-1)(j-1)-(2+(n-1)(i-1))=n-1$, when $3\leq j\leq n$.

This implies that the length of the edge $\phi(v_{i})\phi(v_{j})$ belongs to
$\\{\pm 1,\pm(n-1)\\}$ in both cases, and so $\phi(v_{i})\phi(v_{j})\in
E(\textrm{Ci}[2n,\\{1,n-1\\}])$.

There are no more cases to consider, proving our result.

We next show that the only circulant accordions $A[n,k]$ with both $n$ and $k$
even are the ones having $k=2$. By Lemma 5.2, this means that the only
circulant bipartite accordions are the ones with $n$ even and $k=2$.

######  Lemma 5.6.

For $n$ and $k$ even, the accordion graph $A[n,k]$ is circulant if and only if
$k=2$.

######  Proof 5.7.

Let $n$ and $k$ be even. By Lemma 5.4, it suffices to show that accordion
graphs admitting $k\geq 4$ are not circulant. We can further assume that
$n\geq 8$, since the only accordions with $n=4$ or $6$, and $k$ even are
$A[4,2]$ and $A[6,2]$. Suppose, for contradiction, that for $n\geq 8$, there
exists an even integer $k\geq 4$ such that $A[n,k]$ is circulant. Then, by
Corollary 5.1 and Lemma 5.2, $A[n,k]\simeq\textrm{Ci}[2n,\\{a,b\\}]$ for some
distinct odd integers $a$ and $b$. For simplicity, we refer to $A[n,k]$, or
equivalently $\textrm{Ci}[2n,\\{a,b\\}]$, by $G$. By the definition of quartic
circulant graphs, we recall that $1\leq a<b\leq n-1$.

Claim. $\gcd(2n,a)=\gcd(2n,b)=1$.

_Proof of Claim._ Suppose that $\gcd(2n,a)\not=1$, for contradiction. Then,
the least common multiple of $a$ and $2n$ is $2na^{\prime}$, for some
$a^{\prime}<a$. Consequently, there exists an even integer $p$ such that
$ap=2na^{\prime}$. Moreover, since $a\neq a^{\prime}$ and $a$ is odd,
$\frac{a}{a^{\prime}}$ (or equivalently $\frac{2n}{p}$) is odd and at least
$3$, and so $p<n$. By considering the edges in $G$ having length $a$, there
exists a partition $\mathcal{P}$ of the $2n$ vertices of $G$ into
$\frac{2n}{p}$ sets, each inducing a $p$-cycle. This follows since
$\gcd(2n,a)=\frac{2n}{p}\not=1$. Furthermore, $\mathcal{P}$ has an odd number
of components, namely $\gcd(2n,a)$, or equivalently $\frac{2n}{p}$.

Since $G$ is a connected quartic graph and $\frac{2n}{p}>1$, two vertices on a
particular $p$-cycle in $\mathcal{P}$ are adjacent in $G$ if and only if there
is an edge of length $a$ between them, in other words, the subgraph induced by
the vertices on a $p$-cycle in $\mathcal{P}$ is the $p$-cycle itself.
Therefore, the graph contains two adjacent vertices $x_{i}$ and $x_{j}$
belonging to two different $p$-cycles from $\mathcal{P}$. Consequently, since
$i\equiv j\pm b\pmod{2n}$, the vertices of these two $p$-cycles induce
$C_{p}\square P_{2}$. By a similar argument to that used on $x_{i}$ and
$x_{j}$, we deduce that $G$ contains a spanning subgraph $G_{0}$ isomorphic to
$C_{p}\square P_{\frac{2n}{p}}$.

We now denote the set $\\{u_{1},u_{2},\ldots,u_{n}\\}$ of vertices on the
outer-cycle of $A[n,k]$ by $\mathcal{U}$, and the set
$\\{v_{1},v_{2},\ldots,v_{n}\\}$ of vertices on the inner-cycle of $A[n,k]$ by
$\mathcal{V}$, and claim that:

  1. (i)

given two adjacent vertices from some $p$-cycle in $\mathcal{P}$, say $x_{i}$
and $x_{i+a}$, if $x_{i}$ is a vertex in $\mathcal{U}$, then $x_{i+a}$ is a
vertex in $\mathcal{V}$, or vice-versa; and

  2. (ii)

given two adjacent vertices from two different $p$-cycles in $\mathcal{P}$,
say $x_{i}$ and $x_{i+b}$, we have that either both belong to $\mathcal{U}$ or
both belong to $\mathcal{V}$.

First of all, we note that the vertices inducing a $p$-cycle from
$\mathcal{P}$, cannot all belong to $\mathcal{U}$, since the latter set of
vertices induces a $n$-cycle, and $p<n$. Similarly, the vertices inducing a
$p$-cycle from $\mathcal{P}$, cannot all belong to $\mathcal{V}$. Secondly,
let $i\in[2n]$, such that $x_{i}$ is of degree $3$ in $G_{0}$, and
$x_{i}x_{i+b}\in E(G_{0})$. Consider the $4$-cycle
$(x_{i},x_{i+a},x_{i+a+b},x_{i+b})$. Since $n>4$, these four vertices cannot
all belong to $\mathcal{U}$ (or $\mathcal{V}$). Also, we cannot have three of
them which belong to $\mathcal{U}$ (or $\mathcal{V}$), because otherwise we
would have $k=2$, or, $k\equiv-2\pmod{n}$, that is, $k=n-2$. Since we are
assuming that $k\geq 4$, we must have $k=n-2$, but by Definition 2.1, $k$ is
at most $\frac{n}{2}$, and so, $n-2\leq\frac{n}{2}$, a contradiction, since
$n\geq 8$. This means that exactly two vertices from
$(x_{i},x_{i+a},x_{i+a+b},x_{i+b})$ belong to $\mathcal{U}$, and the other two
belong to $\mathcal{V}$. Without loss of generality, assume that $x_{i}$
belongs to $\mathcal{U}$.

Suppose that $x_{i+b}\not\in\mathcal{U}$, for contradiction. Then,
$\mathcal{U}$ must contain exactly one of $x_{i+a}$ and $x_{i+a+b}$. Suppose
we have $x_{i+a+b}\in\mathcal{U}$. Consequently, $x_{i+a}$ and $x_{i+b}$
belong to $\mathcal{V}$, and so since $\frac{2n}{p}\geq 3$, $x_{i+2a+b}$ and
$x_{i+a+2b}$ belong to $\mathcal{U}$, giving rise to a $4$-cycle in $G_{0}$
with three of its vertices belonging to $\mathcal{U}$, a contradiction.
Therefore, we have $x_{i+a}\in\mathcal{U}$. This means that $x_{i+b}$ and
$x_{i+a+b}$ both belong to $\mathcal{V}$. Suppose further that
$x_{i+2a}\in\mathcal{V}$. Since we cannot have three vertices in a $4$-cycle
belonging to $\mathcal{V}$, $x_{i+2a+b}\in\mathcal{U}$. However, this once
again gives rise to a $4$-cycle in $G_{0}$ with three of its vertices
belonging to $\mathcal{U}$, a contradiction. Therefore, $x_{i+2a}$ must belong
to $\mathcal{U}$. By repeating the same argument used for $x_{i+2a}$ to the
vertices $x_{i+3a},\ldots,x_{i+(p-1)a}$, we get that all the vertices in the
$p$-cycle, from $\mathcal{P}$, containing $x_{i}$ belong to $\mathcal{U}$, a
contradiction. Hence, $x_{i+a}\not\in\mathcal{U}$. Thus, neither one of
$x_{i+a}$ and $x_{i+a+b}$ is in $\mathcal{U}$, contradicting our initial
assumption. This implies that $x_{i+b}\in\mathcal{U}$, and that $x_{i\pm a}$
and $x_{i+b\pm a}$ belong to $\mathcal{V}$. This forces all the vertices not
considered so far to satisfy the two conditions in the above claim.

Thus, by Remark 2.2, $\frac{2n}{p}=\gcd(n,k)$. This is a contradiction, since
$\frac{2n}{p}$ is odd and the greatest common divisor of two even numbers is
even. Hence, $\gcd(2n,a)=1$, and by a similar reasoning, $\gcd(2n,b)=1$ as
well. $\blacksquare$

This implies that $a$ does not divide $n$, $b$ does not divide $n$, and that
the edges of $G$ can be partitioned in two Hamiltonian cycles induced by the
edges having length $a$ and $b$, respectively.

In particular, since $a$ does not divide $2n$, there exists an edge of length
$a$ with both endvertices belonging to $\\{u_{i}:i\in[n]\\}\subset V(A[n,k])$.
Without loss of generality, assume that $u_{1}u_{2}$ has length $a$, and
consider the $4$-cycle $C=(u_{1},u_{2},v_{2},v_{1})$. Since the edges having
length $a$ (and similarly the edges having length $b$) induce a Hamiltonian
cycle, and $n>4$, the lengths of the edges in $C$ cannot all be the same.
Hence, the lengths of the edges
$(u_{1}u_{2},u_{2}v_{2},v_{2}v_{1},v_{1}u_{1})$ of $C$ can be of Type A1
$:=(a,b,b,b)$, Type A2 $:=(a,a,b,a)$, Type A3 $:=(a,a,a,b)$, Type A4
$:=(a,b,a,a)$, Type B1 $:=(a,a,b,b)$, Type B2 $:=(a,b,b,a)$, or Type B3
$:=(a,b,a,b)$. Some of these types are depicted in Figure 7.

Figure 7: Different lengths of the edges in $C$

If $C$ is of Type A1, then $a\equiv\pm 3b\pmod{2n}$. This implies that the two
endvertices of an edge of length $a$ are also endvertices of a $3$-path whose
edges are all of length $b$. Also, the two endvertices of a $3$-path whose
edges are all of length $b$ must be adjacent. Consider the edge $v_{2}v_{3}$.
Since $v_{1}v_{2}$ and $u_{2}v_{2}$ have length $b$, the edge $v_{2}v_{3}$ has
length $a$, and so it must belong to some $4$-cycle with the other three edges
of the cycle having length $b$. We denote this $4$-cycle by
$C_{4}(v_{2}v_{3})$. First, assume that $u_{2}u_{3}$ is of length $a$. If
$u_{2}v_{2}\in E(C_{4}(v_{2}v_{3}))$, then, $E(C_{4}(v_{2}v_{3}))$ contains
$u_{2}v_{2+k}$ and consequently $v_{2+k}v_{3}$, which is impossible, since
$k\geq 4$. Therefore, $E(C_{4}(v_{2}v_{3}))$ contains $v_{1}v_{2}$, and so
$C_{4}(v_{2}v_{3})=(v_{3},v_{2},v_{1},u_{1})$, implying that $k=2$, a
contradiction. Consequently, $u_{2}u_{3}$ must be of length $b$, implying that
$C_{4}(v_{2}v_{3})=(v_{3},v_{2},u_{2},u_{3})$. By using the same arguments we
can deduce that the outer- and inner-cycle edges, and the vertical spokes in
$G$ have lengths as shown in Figure 8.

Figure 8: $A[n,k]$ when $C$ is of Type A1

Since $k$ is even, we also have $b\equiv\pm 3a\pmod{2n}$ (see for example the
$4$-cycle $(u_{1},u_{2},\linebreak v_{2+k},v_{1+k})$). This implies that
$a\equiv\pm 9a\pmod{2n}$, that is, $8a\equiv 2n\pmod{2n}$, or $10a\equiv
2n\pmod{2n}$. Since $\gcd(2n,a)=1$, the total number of vertices of $G$ must
be equal to $8$ or $10$, a contradiction, since $n\geq 8$.

If $C$ is of Type A2, then $b\equiv\pm 3a\pmod{2n}$. This implies that the two
endvertices of an edge of length $b$ are also endvertices of a $3$-path whose
edges are all of length $a$. Also, the two endvertices of a $3$-path whose
edges are all of length $a$ must be adjacent. Consider the edge $u_{2}u_{3}$.
Since $u_{1}u_{2}$ and $u_{2}v_{2}$ have length $a$, the edge $u_{2}u_{3}$ has
length $b$, and so it must belong to some $4$-cycle with the other three edges
of the cycle having length $a$. We denote this $4$-cycle by
$C_{4}(u_{2}u_{3})$. First, assume that $v_{2}v_{3}$ is of length $b$. If
$u_{2}v_{2}\in E(C_{4}(u_{2}u_{3}))$, then, $E(C_{4}(u_{2}u_{3}))$ contains
$v_{2}u_{2-k}$ and consequently $u_{2-k}u_{3}$. This means that
$u_{2-k}=u_{4}$, and so, since $u_{4}$ is adjacent to $v_{2}$ we have that
$k\equiv-2\pmod{n}$. By Definition 2.1, this implies that
$k=n-2\leq\frac{n}{2}$, a contradiction since $n\geq 8$. Therefore,
$E(C_{4}(u_{2}u_{3}))$ contains $u_{1}u_{2}$, and so
$C_{4}(u_{2}u_{3})=(u_{3},u_{2},u_{1},v_{1})$, implying once again that
$k\equiv-2\pmod{n}$, a contradiction. Consequently, $v_{2}v_{3}$ must be of
length $a$, implying that $C_{4}(u_{2}u_{3})=(u_{3},u_{2},v_{2},v_{3})$. By
using the same arguments we can deduce that the outer- and inner-cycle edges,
and the vertical spokes in $G$ have lengths as shown in Figure 9.

Figure 9: $A[n,k]$ when $C$ is of Type A2

Since $k$ is even, we also have $a\equiv\pm 3b\pmod{2n}$ (see for example the
$4$-cycle $(u_{2},u_{3},\linebreak v_{3+k},v_{2+k})$). This once again implies
that $a\equiv\pm 9a\pmod{2n}$, a contradiction as in the case when $C$ is of
Type A1.

So assume that $C$ is of Type A3. Then, $b\equiv\pm 3a\pmod{2n}$ and, in
particular, the edge $u_{2}u_{3}$ has length $b$. Consequently, this edge must
belong to some $4$-cycle with the other three edges of the cycle having length
$a$. We denote this $4$-cycle by $C_{4}(u_{2}u_{3})$. Since $u_{1}u_{2}$ and
$u_{2}v_{2}$ are both of length $a$, we have the following cases:

  * •

if $C_{4}(u_{2}u_{3})=(u_{3},u_{2},u_{1},v_{1+k})$, then $k=2$, a
contradiction;

  * •

if $C_{4}(u_{2}u_{3})=(u_{3},u_{2},u_{1},u_{n})$, then $n=4$, a contradiction;
and

  * •

if $C_{4}(u_{2}u_{3})=(u_{3},u_{2},v_{2},v_{1})$, then $u_{3}$ is adjacent to
$v_{1}$. Consequently, we have that $k\equiv-2\pmod{n}$, and as before, this
implies that $n-2\leq\frac{n}{2}$, a contradiction, since $n\geq 8$.

Thus $C$ cannot be of Type A3, and by using a similar argument, it can be
shown that $C$ cannot be of Type A4 either. In fact, if $C$ is of Type A4,
then, $b\equiv\pm 3a\pmod{2n}$ once again, and, in particular, the edge
$u_{1}u_{n}$ has length $b$. Consequently, this edge must belong to some
$4$-cycle with the other three edges of the cycle having length $a$. We denote
this $4$-cycle by $C_{4}(u_{1}u_{n})$. Since $u_{1}u_{2}$ and $u_{1}v_{1}$ are
both of length $a$, we have the following cases:

  * •

if $C_{4}(u_{1}u_{n})=(u_{n},u_{1},v_{1},v_{2})$, then $k=2$, a contradiction;

  * •

if $C_{4}(u_{1}u_{n})=(u_{n},u_{1},u_{2},u_{3})$, then $n=4$, a contradiction;
and

  * •

if $C_{4}(u_{1}u_{n})=(u_{n},u_{1},u_{2},v_{2+k})$, then $u_{n}$ is adjacent
to $v_{2+k}$. Consequently, we have that $k\equiv-2\pmod{n}$, and as before,
this implies that $n-2\leq\frac{n}{2}$, a contradiction, since $n\geq 8$.

Thus, $C$ cannot be of Type A4. If $C$ is of Type B1 or Type B2, then we have
that $2a\equiv\pm 2b\pmod{2n}$, and since $1\leq a<b\leq n-1$, we can further
assume that $2a\equiv-2b\pmod{2n}$. Consequently, we have that $a+b=n$, and
so, since $\gcd(2n,a)=\gcd(2n,b)=\gcd(2n,1)=\gcd(2n,n-1)=1$, by Lemma 5.4,
$G\simeq A[n,2]$, a contradiction. Therefore, $C$ and all other possible
$4$-cycles in $G$ must be of Type B3, which is impossible, because then the
edges having length $a$ would induce two disjoint $n$-cycles, contradicting
the fact that the edges having length $a$ induce a Hamiltonian cycle (and thus
a $2n$-cycle). As a consequence, $A[n,k]$ is not circulant, contradicting our
initial assumption.

Using the above two lemmas we can now prove the main result of this section.

######  Theorem 5.8.

The accordion graph $A[n,k]$ is not circulant if and only if both $n$ and $k$
are even, such that $k\geq 4$.

######  Proof 5.9.

By Lemma 5.6, it suffices to show that the accordion graph $A[n,k]$ is
circulant if and only if either

  1. (i)

$k$ is odd, or

  2. (ii)

$k$ is even and $n$ is odd, or

  3. (iii)

$k=2$ and $n$ is even.

Case (i). For $k$ odd, we claim that the function $\phi:V(A[n,k])\rightarrow
V(\textrm{Ci}[2n,\\{2,k\\}])$ defined by $\phi:u_{i}\mapsto x_{2i}$ and
$\phi:v_{i}\mapsto x_{2i-k\pmod{2n}}$, where $i\in[n]$, is an isomorphism.
Since $2i-k$ is odd, for every $i\in[n]$, one can deduce that the function
$\phi$ is bijective. Also, $\textrm{Ci}[2n,\\{2,k\\}]$ has the same number of
edges as $A[n,k]$, and thus it suffices to show that an edge in $A[n,k]$ is
mapped to an edge in $\textrm{Ci}[2n,\\{2,k\\}]$.

  1. (a)

We first take an edge $u_{i}u_{j}$ from the outer-cycle of $A[n,k]$, for some
$i\in[n]$ and $j\equiv i+1\pmod{n}$, without loss of generality. Consider
$\phi(u_{i})\phi(u_{j})$. The length of $\phi(u_{i})\phi(u_{j})$ can be
calculated using $2(j-i)$ which is equivalent to $2\pmod{2n}$. Since this
belongs to $\\{\pm 2,\pm k\\}$, $\phi(u_{i})\phi(u_{j})\in
E(\textrm{Ci}[2n,\\{2,k\\}])$.

  2. (b)

By a similar reasoning to that used in (a), $\phi(v_{i})\phi(v_{j})$ is an
edge in $\textrm{Ci}[2n,\\{2,k\\}]$, for any $i\in[n]$ and $j\equiv
i+1\pmod{n}$, without loss of generality.

  3. (c)

We now consider the spokes. Let $i\in[n]$ and $j\equiv i+k\pmod{n}$. The
length of $\phi(u_{i})\phi(v_{i})$ can be calculated using $2i-k-2i$, which is
equal to $-k$. On the other hand, the length of $\phi(u_{i})\phi(v_{j})$ can
be calculated using $2j-k-2i$, which is equal to $k$. In both cases, the
lengths obtained belong to $\\{\pm 2,\pm k\\}$, and so
$\phi(u_{i})\phi(v_{i})$ and $\phi(u_{i})\phi(v_{j})$ are edges in
$\textrm{Ci}[2n,\\{2,k\\}]$.

Case (ii). For $k$ even and $n$ odd, we claim that the following function
$\phi:V(A[n,k])\rightarrow V(\textrm{Ci}[2n,\\{2,n-k\\}])$ defined by
$\phi:u_{i}\mapsto x_{2i}$ and $\phi:v_{i}\mapsto x_{2i+n-k\pmod{2n}}$, where
$i\in[n]$, is an isomorphism. As in Case (i), the function $\phi$ is
bijective, since $n-k$ is odd. Moreover, $\textrm{Ci}[2n,\\{2,n-k\\}]$ has the
same number of edges as $A[n,k]$, and so it suffices to show that an edge in
$A[n,k]$ is mapped to an edge in $\textrm{Ci}[2n,\\{2,n-k\\}]$.

  1. (a)

By the same reasoning used in Case (i), $\phi(u_{i})\phi(u_{j})$ and
$\phi(v_{i})\phi(v_{j})$ are edges in $\textrm{Ci}[2n,\\{2,n-k\\}]$, for
$i\in[n]$, and $j\equiv i+1\pmod{n}$, without loss of generality.

  2. (b)

We now consider the spokes. Let $i\in[n]$ and $j\equiv i+k\pmod{n}$. The
length of $\phi(u_{i})\phi(v_{i})$ can be calculated using $2i+n-k-2i$, which
is equal to $n-k$. On the other hand, the length of $\phi(u_{i})\phi(v_{j})$
can be calculated using $2j+n-k-2i$, which is equivalent to $-(n-k)\pmod{2n}$.
In both cases, the lengths obtained belong to $\\{\pm 2,\pm(n-k)\\}$, and so
$\phi(u_{i})\phi(v_{i})$ and $\phi(u_{i})\phi(v_{j})$ are edges in
$\textrm{Ci}[2n,\\{2,n-k\\}]$.

Case (iii). This was proven in Lemma 5.4.

The following result follows immediately from the proof of Theorem 5.8.

######  Corollary 5.10.

The accordion graph $A[n,k]$ is isomorphic to the circulant graph

  1. (i)

$\textrm{Ci}[2n,\\{2,k\\}]$, when $k$ is odd;

  2. (ii)

$\textrm{Ci}[2n,\\{2,n-k\\}]$, when $n$ is odd and $k$ is even; and

  3. (iii)

$\textrm{Ci}[2n,\\{1,n-1\\}]$, when $n$ is even and $k=2$.

##  6 Concluding remarks and open problems

Despite ruling out all accordion graphs $A[n,k]$ having $\gcd(n,k)\geq 5$, a
complete characterisation of which accordion graphs have the PMH- or the PH-
property is definitely of interest but still inaccessible. In Section 3,
partial results were obtained for the cases when $\gcd(n,k)\leq 2$. These are
portrayed in Table 1 together with other partial results obtained by a
computer check conducted through Wolfram Mathematica. In particular, we
identify which accordions are PMH and which are not, for $1\leq k\leq 10$ and
for $n\leq 21$. We remark that some values of $n$ and $k$ are marked as
“unknown” due to problems with computation time and memory.

$A[n,k]$ | $k$ |  |  |  |
---|---|---|---|---|---
|  | $1$ | $2$ | $3$ | $4$ | $5$ | $6$ | $7$ | $8$ | $9$ | $10$ |  |  |
$n$ | $3$ |  |  |  |  |  |  |  |  |  |  |  |  |
$4$ |  |  |  |  |  |  |  |  |  |  |  |  |
$5$ |  |  |  |  |  |  |  |  |  |  |  |  |
$6$ |  |  |  |  |  |  |  |  |  |  |  |  |
$7$ |  |  |  |  |  |  |  |  |  |  |  |  |
$8$ |  |  |  |  |  |  |  |  |  |  |  |  |
$9$ |  |  |  |  |  |  |  |  |  |  |  |  |
$10$ |  |  |  |  | $\bot$ |  |  |  |  |  |  |  |
$11$ |  |  |  |  |  |  |  |  |  |  |  |  |  $A[n,k]$ PMH
$12$ |  |  |  |  |  | $\bot$ |  |  |  |  |  | $\bot$ |  $A[n,k]$ not PMH
$13$ |  |  | $\bot$ |  |  |  |  |  |  |  |  | ? | Unknown
$14$ |  |  | $\bot$ |  |  |  | $\bot$ |  |  |  |  |  |
$15$ |  |  | $\bot$ | $\bot$ | $\bot$ |  |  |  |  |  |  |  |
$16$ |  |  | $\bot$ |  |  |  | $\bot$ | $\bot$ |  |  |  |  |
$17$ |  |  | $\bot$ | $\bot$ | $\bot$ | $\bot$ |  |  |  |  |  |  |
$18$ |  |  | $\bot$ |  | $\bot$ | $\bot$ | $\bot$ | ? | $\bot$ |  |  |  |
$19$ |  |  | $\bot$ | $\bot$ | $\bot$ | $\bot$ | $\bot$ | $\bot$ | $\bot$ |  |  |  |
$20$ |  |  | $\bot$ | ? | $\bot$ | ? | $\bot$ | ? | $\bot$ | $\bot$ |  |  |
$21$ |  |  | $\bot$ | $\bot$ | $\bot$ | $\bot$ | $\bot$ | ? | ? | ? |  |  |
Table 1: Which accordions are PMH for $3\leq n\leq 21$ and $1\leq k\leq 10$

Additionally, as already remarked before, the main result in [4] gives more
than just all the possible values of $n_{1}$ and $n_{2}$, for which
$C_{n_{1}}\square C_{n_{2}}$ is circulant. In fact, the main result of the
above paper is the following.

######  Theorem 6.1.

[4] The circulant graph $\textrm{Ci}[n^{\prime},\\{a_{1},a_{2}\\}]$ is
isomorphic to $C_{n_{1}}\square C_{n_{2}}$ if and only if:

  1. (i)

$n^{\prime}=n_{1}n_{2}$,

  2. (ii)

$n_{1}=\gcd(n^{\prime},a_{j})$ and $n_{2}=\gcd(n^{\prime},a_{3-j})$, where
$j=1$ or $j=2$, and

  3. (iii)

$\gcd(n_{1},n_{2})=1$.

In this sense, we think that it would be an interesting endeavour to give a
necessary and sufficient condition for a quartic circulant graph to be
isomorphic to some accordion.

## References

  * [1] M. Abreu, J.B. Gauci, D. Labbate, G. Mazzuoccolo and J.P. Zerafa, Extending perfect matchings to Hamiltonian cycles in line graphs, _Electron. J. Combin._ 28(1) (2021), #P1.7.
  * [2] A. Alahmadi, R.E.L. Aldred, A. Alkenani, R. Hijazi, P. Solé and C. Thomassen, Extending a perfect matching to a Hamiltonian cycle, _Discrete Math. Theor. Comput. Sci._ 17(1) (2015), 241–254.
  * [3] F. Boesch and R. Tindell, Circulants and their connectivities, _J. Graph Theory_ 8 (1984), 487–499.
  * [4] Z.R. Bogdanowicz, On isomorphism between circulant and Cartesian product of 2 cycles, _Discrete Appl. Math._ 194 (2015), 160–162.
  * [5] R. Diestel, _Graph Theory_ , Graduate Texts in Mathematics 173, Springer-Verlag, New York, 2000.
  * [6] J. Fink, Perfect matchings extend to Hamilton cycles in hypercubes, _J. Comb. Theory, Ser. B_ 97(6) (2007), 1074–1076.
  * [7] J.B. Gauci and J.P. Zerafa, Perfect Matchings and Hamiltonicity in the Cartesian Product of Cycles, _Ann. Comb._ 25 (2021), 789–796, https://doi.org/10.1007/s00026-021-00548-1.
  * [8] R. Häggkvist, On $F$-Hamiltonian graphs, in: J.A. Bondy, U.S.R. Murty (eds.), _Graph Theory and Related Topics_ , Academic Press, New York, 1979, 219–231.
  * [9] S. Herke and B. Maenhaut, Perfect 1-Factorisations of Circulants with Small Degree, _Electron. J. Combin_ 20(1) (2013), $\\#$P58.
  * [10] C. Heuberger, On planarity and colorability of circulant graphs, _Discrete Math._ 268 (2003), 153–169.
  * [11] M. Las Vergnas, _Problèmes de couplages et problèmes hamiltoniens en théorie des graphes_ , Thesis, University of Paris 6, Paris, 1972.