On the number of edge-disjoint one factors and the existence of k-factors in complete multipartite graphs |
| |
Authors: | D G Hoffman and C A Rodger |
| |
Institution: | Department of Discrete and Statistical Sciences. Auburn University, Auburn, AL 36849-5307, USA |
| |
Abstract: | In this paper we use Tutte's f-factor theorem and the method of amalgamations to find necessary and sufficient conditions for the existence of a k-factor in the complete multipartite graph K(p(1), …, p(n)), conditions that are reminiscent of the Erdös-Gallai conditions for the existence of simple graphs with a given degree sequence. We then use this result to investigate the maximum number of edge-disjoint 1-factors in K(p(1), …, p(n)), settling the problem in the case where this number is greater than δ - p(2), where p(1) p(2) … p(n). |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|