Moshe Rosenfeld ; Ziqing Xiang - Hamiltonian decomposition of prisms over cubic graphs

dmtcs:2079 - Discrete Mathematics & Theoretical Computer Science, May 11, 2015, Vol. 16 no. 2 - https://doi.org/10.46298/dmtcs.2079
Hamiltonian decomposition of prisms over cubic graphs

Authors: Moshe Rosenfeld ; Ziqing Xiang

    The prisms over cubic graphs are 4-regular graphs. The prisms over 3-connected cubic graphs are Hamiltonian. In 1986 Brian Alspach and Moshe Rosenfeld conjectured that these prisms are Hamiltonian decomposable. In this paper we present a short survey of the status of this conjecture, various constructions proving that certain families of prisms over 3-connected cubic graphs are Hamiltonian decomposable. Among others, we prove that the prisms over cubic Halin graphs, cubic generalized Halin graphs of order 4k + 2 and other infinite sequences of cubic graphs are Hamiltonian decomposable.


    Volume: Vol. 16 no. 2
    Section: PRIMA 2013
    Published on: May 11, 2015
    Submitted on: November 28, 2013
    Keywords: Graph theory,[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]

    Consultation statistics

    This page has been seen 404 times.
    This article's PDF has been downloaded 633 times.