Perfect matchings and Hamiltonicity in the Cartesian product of cycles

A pairing of a graph \(G\) is a perfect matching of the complete graph having the same vertex set as \(G\). If every pairing of \(G\) can be extended to a Hamiltonian cycle of the underlying complete graph using only edges from \(G\), then \(G\) has the PH-property. A somewhat weaker property is the...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2020-05
Main Authors: Gauci, John Baptist, Zerafa, Jean Paul
Format: Article
Language:English
Subjects:
Apexes
Cartesian coordinates
Graph matching
Graph theory
Traveling salesman problem
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:A pairing of a graph \(G\) is a perfect matching of the complete graph having the same vertex set as \(G\). If every pairing of \(G\) can be extended to a Hamiltonian cycle of the underlying complete graph using only edges from \(G\), then \(G\) has the PH-property. A somewhat weaker property is the PMH-property, whereby every perfect matching of \(G\) can be extended to a Hamiltonian cycle of \(G\). In an attempt to characterise all 4-regular graphs having the PH-property, we answer a question made in 2015 by Alahmadi et al. by showing that the Cartesian product \(C_p\square C_q\) of two cycles on \(p\) and \(q\) vertices does not have the PMH-property, except for \(C_4\square C_4\) which is known to have the PH-property.
ISSN:2331-8422
DOI:10.48550/arxiv.2005.02913