Seminar of Graph Theory - Jean Paul Zerafa (24.2.2022)
Thursday 24.2.2022 at 9:50, Lecture room M/213
Jean Paul Zerafa:
Tweaking the Cartesian product of two cycles
Abstract:
Let G be a graph admitting a perfect matching. A pairing of a graph G is a perfect matching of the complete graph on the same vertex set of G, and a graph is said to have the Pairing-Hamiltonian property if for every pairing of G there exists a perfect matching of G such that their union gives a Hamiltonian cycle. After having characterised which 3-regular graphs have the Pairing-Hamiltonian property, in [Discrete Math. Theor. Comput. Sci. 17(1) (2015)], Alahmadi et al. suggest trying to tackle this characterisation problem for 4-regular graphs by looking at the Cartesian product of cycles CpCq. We show that the only such graph admitting the Pairing-Hamiltonian property is C4C4, that is, the 4-dimensional hypercube. However, by slightly replacing some adjacencies in CpCq one can obtain what we define accordion graphs, which are 4-regular graphs on two parameters, n and k, denoted by A[n, k]. For every n ≥ 4, A[n, 2] has the Pairing-Hamiltonian property and empirical evidence suggests that, apart from A[n, 2], there are (possibly an infinite number of) other accordion graphs having such a property or similar ones. Furthermore, once the accordion graph A[n, 2] is drawn, one can immediately notice that it is a circulant graph. In [Discrete Appl. Math. 194 (2015)], Bogdanowicz gave a necessary and sufficient condition for a 4-regular circulant graph to be isomorphic to the Cartesian product of two cycles. In a similar way, we determine which accordion graphs are circulant, and also give all the possible values a 4-regular circulant graph can admit for it to be isomorphic to an accordion graph.
The above problems are joint work with John B. Gauci from L-Universit`a ta’ Malta.