On 2-factors containing 1-factors in bipartite graphs

Moon and Moser (Israel J. Math. 1 (1962) 163–165) showed that if G is a balanced bipartite graph of order 2 n and minimum degree σ ⩾ ( n + 1)/2, then G is hamiltonian. Recently, it was shown that their well-known degree condition also implies the existence of a 2-factor with exactly k cycles provide...

Full description

Saved in:
Bibliographic Details
Published in:Discrete mathematics 1999-02, Vol.197, p.185-194
Main Authors: Chen, Guantao, Gould, Ronald J., Jacobson, Michael S.
Format: Article
Language:English
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Moon and Moser (Israel J. Math. 1 (1962) 163–165) showed that if G is a balanced bipartite graph of order 2 n and minimum degree σ ⩾ ( n + 1)/2, then G is hamiltonian. Recently, it was shown that their well-known degree condition also implies the existence of a 2-factor with exactly k cycles provided n ⩾ max {52, 2 k 2 + 1}. In this paper, we show that a similar degree condition implies that for each perfect matching M, there exists a 2-factor with exactly k cycles including all edges of M.
ISSN:0012-365X
1872-681X
DOI:10.1016/S0012-365X(99)90061-4