论文标题
手风琴图：汉密尔顿，匹配和同构与四分之一循环器
Accordion graphs: Hamiltonicity, matchings and isomorphism with quartic circulants
论文作者
论文摘要
令$ g $为偶数的图表，让$ k_ {g} $为$ g $的同一顶点集上的完整图。图$ g $的配对是图$ k_ {g} $的完美匹配。图$ g $具有配对的汉密尔顿属性（简称为ph-property），如果对于每个配对，则存在$ g $的完美匹配，从而使两者的结合产生了汉密尔顿周期的$ k_g $。在2015年，Alahmadi \ emph {et al。}给出了具有pH-property的立方图的完整表征。最自然的是，下一步是表征具有pH-property的四分之一的图形。在这项工作中，我们建议在两个参数（$ n $ and $ k $）上提出一类四分之一的图形，我们将其称为“手风琴图” $ a [n，k] $。我们表明，Alahmadi \ emph {et al。}的无限图（也是循环）的无限家族称其实际上是该一般的手风琴图类别的成员。我们还研究了此类手风琴图的pH杂质，有时考虑到$ g $的配对，这也是$ g $的完美匹配。此外，手风琴图与两个周期的笛卡尔产物之间存在密切的关系。由Bogdanowicz（2015）最近的一项工作的动机，我们对那些是循环图的手风琴图进行了完整的表征。实际上，我们表明$ a [n，k] $不是且仅当$ n $和$ k $都均匀时，因此$ k \ geq 4 $。
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 \emph{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 \emph{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$.
