On the perfect 1-factorisation problem for circulant graphs of degree 4

Herke, Sarada (2014) On the perfect 1-factorisation problem for circulant graphs of degree 4. Australasian Journal of Combinatorics, 60 79-108.

Attached Files (Some files may be inaccessible until you login with your UQ eSpace credentials)
Name Description MIMEType Size Downloads
UQ377805_OA.pdf Full text (open access) application/pdf 630.87KB 0
Author Herke, Sarada
Title On the perfect 1-factorisation problem for circulant graphs of degree 4
Journal name Australasian Journal of Combinatorics   Check publisher's open access policy
ISSN 2202-3518
Publication date 2014-01-01
Sub-type Article (original research)
Open Access Status File (Publisher version)
Volume 60
Start page 79
End page 108
Total pages 30
Place of publication University Of Queensland, Brisbane, Australia
Publisher Centre for Discrete Mathematics & Computing
Language eng
Formatted abstract
A 1-factorisation of a graph G is a partition of the edge set of G into 1-factors (perfect matchings); a perfect 1-factorisation of G is a 1-factorisation of G in which the union of any two of the 1-factors is a Hamilton cycle in G. It is known that for bipartite 4-regular circulant graphs, having order 2 (mod 4) is a necessary (but not sufficient) condition for the existence of a perfect 1-factorisation. The only known non-bipartite 4-regular circulant graphs that admit a perfect 1-factorisation are trivial (on 6 vertices). We prove several construction results for perfect 1-factorisations of a large class of bipartite 4-regular circulant graphs. In addition, we show that no member of an infinite family of non-bipartite 4-regular circulant graphs admits a perfect 1-factorisation. This supports the conjecture that there are no perfect 1-factorisations of any connected non-bipartite 4-regular circulant graphs of order at least 8.
Q-Index Code C1
Q-Index Status Provisional Code
Institutional Status Unknown

Document type: Journal Article
Sub-type: Article (original research)
Collection: School of Mathematics and Physics
Version Filter Type
Citation counts: Scopus Citation Count Cited 0 times in Scopus Article
Google Scholar Search Google Scholar
Created: Thu, 28 Jan 2016, 21:04:43 EST by Kay Mackie on behalf of School of Mathematics & Physics