Factoring the cartesian product of a cubic graph and a triangle

Kotzig asked: does the cartesian product of a bridgeless cubic graph with a triangle always have a one-factorization? We answer this in the affirmative. Indeed the cartesian product of a 3-connected cubic graph with a triangle can be factored into two Hamilton cycles and a one-factor.

Saved in:
Bibliographic Details
Published in:Discrete mathematics 2002-12, Vol.259 (1), p.137-146
Main Authors: Horton, J.D., Wallis, W.D.
Format: Article
Language:English
Subjects:
Combinatorics
Combinatorics. Ordered structures
Exact sciences and technology
Graph theory
Mathematics
Sciences and techniques of general use
Citations: Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Kotzig asked: does the cartesian product of a bridgeless cubic graph with a triangle always have a one-factorization? We answer this in the affirmative. Indeed the cartesian product of a 3-connected cubic graph with a triangle can be factored into two Hamilton cycles and a one-factor.
ISSN:0012-365X
1872-681X
DOI:10.1016/S0012-365X(02)00376-X