{"id":"arxiv/2609.21682","url":"https://arxiv.org/abs/2609.21682","tags":["math.CO"],"score":0,"title":"The Pairing-Hamiltonian property in Cartesian products of graphs","domain":"math.CO","source":"arxiv","authors":["Federico Romaniello"],"reviews":0,"subject":"math.CO","summary":"Let $G$ be a simple graph of even order at least four, and let $K_G$ denote the complete graph on $V(G)$. A perfect matching of $K_G$ is called a pairing of $G$. The graph $G$ has the Pairing-Hamiltonian property, or PH-property, if every pairing $M$ of $G$ admits a perfect matching $N\\subseteq E(G)$, disjoint from $M$, such that $M\\cup N$ is a Hamiltonian cycle of $K_G$. We prove that the PH-property is preserved under Cartesian products. More precisely, for graphs $G$ and $H$ of even order at least four, we show that both $G$ and $H$ are PH if and only if every pairing of $G\\square H$…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-09-18","reactions":{}}