Perfect Matching and Hamiltonan Cycles in Cubic Graphs

A simple graph has the Perfect Matching Hamiltonian Property (for short the PMH-Property) if each of its perfect matchings can be extended to a Hamiltonian Cycle. Although it is natural to ask for graph with such a property, it turns out to be very difficult to find them in the cubic non-bipartite case with non-trivial edge connectivity; let alone trying to characterise cubic PMH-graphs, which for now is intangible. In this brief talk, we will first go through the basic properties and the well-known examples of these graphs, focusing also on the related structural problems that arise. Finally, we will present an infinite family of cubic non-bipartite graphs with the desired PMH property. During the presentation, further questions and open problems will be discussed.

Join Zoom Meeting
https://univr.zoom.us/j/88082850705

Meeting ID: 880 8285 0705