International Journal of Mathematics and Mathematical Sciences
Volume 2005 (2005), Issue 6, Pages 863-873
doi:10.1155/IJMMS.2005.863
A degree condition for the existence of k-factors with prescribed properties
Department of Mathematics and Statistics, Dalhousie University, Halifax B3H 3J5, NS, Canada
Received 27 July 2004; Revised 26 December 2004
Copyright © 2005 Changping Wang. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.
Abstract
Let k be an integer such that k≥3, and let G be a 2-connected graph of order n with n≥4k+1, kn even, and minimum degree at least k+1. We prove that if the maximum degree
of each pair of nonadjacent vertices is at least n/2, then G has a k-factor excluding any given edge. The result of
Nishimura (1992) is improved.