The Pairing-Hamiltonian property in Cartesian products of graphs

Federico Romaniello

In the authors' words

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 □ 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.

Main resultLimitation the authors admit

The Pairing-Hamiltonian property in Cartesian products of graphs

In the authors' words

More on Combinatorics & discrete math that day

Condensed configurations and valuative matroid invariants

Finite deletion-induced saturation for every non-complete graph

Wild frieze patterns over the integers

Automorphism groups of Cayley graphs on almost simple groups with normal connection sets

On the Word-Representability of Tensor Product Graphs