Skip to content
DraconiticResearch
Search Sources API
203,234 studies31 sourcesUpdated 27 min ago
PreprintCC BY 4.0arXiv

The Pairing-Hamiltonian property in Cartesian products of graphs

  • Federico Romaniello
Open at sourcePDFDOICite

Abstract

Let G be a simple graph of even order at least four, and let KG denote the complete graph on V(G). A perfect matching of KG 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⊆ E(G), disjoint from M, such that M∪ N is a Hamiltonian cycle of KG. 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□ H admits a Hamiltonian completion contained in a spanning union of vertex-disjoint prisms determined by a perfect matching of G or of H. Without this support restriction, the converse fails: a Cartesian product may be PH even when neither of the two graphs is PH.

Related

  1. Well-Covered Powers: Cartesian Products and Cayley Graphs
    Haobo Ma, Thanh Vu, Wenlin Zhang
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv
  2. Covering Families for DP-Coloring of Cartesian Products with Complete Bipartite Graphs
    Hemanshu Kaul, Jeffrey A. Mudrock, Emily A. Psyhogios +3
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  3. On k-limited domination: complexity and Cartesian products
    Aleksandra Tepeh
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv
  4. Sn-equivariant L-classes of Cartesian powers of Witt spaces and the Hodge index conjecture for symmetric products
    Mohammadali Aligholi
    arXivPreprintCC BY 4.0Full textAlgebra & number theoryGeometry & topologyarXiv
  5. Coded Computing for Dynamic System via Cartesian Products
    Chenglin Li, Minquan Cheng, Youlong Wu
    arXivPreprintarXiv licenceFull textGeneral mathematicsarXiv

Cite

BibTeXRIS
BibTeX
@misc{romaniello2026pairinghamiltonian,
  title = {{The Pairing-Hamiltonian property in Cartesian products of graphs}},
  author = {Federico Romaniello},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2609.21682},
  eprint = {2609.21682},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.21682},
  note = {CC BY 4.0},
}
RIS
TY  - UNPB
TI  - The Pairing-Hamiltonian property in Cartesian products of graphs
AU  - Federico Romaniello
PY  - 2026
DA  - 2026/09/18
PB  - arXiv
DO  - 10.48550/arxiv.2609.21682
UR  - https://arxiv.org/abs/2609.21682
AB  - 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⊆ E(G), disjoint from M, such that M∪ 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□ H admits a Hamiltonian completion contained in a spanning union of vertex-disjoint prisms determined by a perfect matching of G or of H. Without this support restriction, the converse fails: a Cartesian product may be PH even when neither of the two graphs is PH.
ER  -