Search

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., 6 pages, 2 figures

In 1994, it was conjectured by Fan and Raspaud that every simple bridgeless cubic graph has three perfect matchings whose intersection is empty. In this paper we answer a question recently proposed by Mkrtchyan and Vardanyan, by giving an equivalent formulation of the Fan-Raspaud Conjecture. We also study a possibly weaker conjecture originally proposed by the first author, which states that in every simple bridgeless cubic graph there exist two perfect matchings such that the complement of their union is a bipartite graph. Here, we show that this conjecture can be equivalently stated using a variant of Petersen-colourings, we prove it for graphs having oddness at most four and we give a natural extension to bridgeless cubic multigraphs and to certain cubic graphs having bridges., 17 pages, 11 figures

A graph admitting a perfect matching has the Perfect-Matching-Hamiltonian property (for short the PMH-property) if each of its perfect matchings can be extended to a Hamiltonian cycle. In this paper we establish some sufficient conditions for a graph $G$ in order to guarantee that its line graph $L(G)$ has the PMH-property. In particular, we prove that this happens when $G$ is (i) a Hamiltonian graph with maximum degree at most $3$, (ii) a complete graph, or (iii) an arbitrarily traceable graph. Further related questions and open problems are proposed along the paper., Comment: 12 pages, 4 figures