On the 1-factors of n-connected graphs |
| |
Authors: | Joseph Zaks |
| |
Affiliation: | 1. University of Washington, Seattle, Washington 98195, USA;2. Wayne State University, Detroit, Michigan 48202 USA |
| |
Abstract: | L. W. Beineke and M. D. Plummer have recently proved [1] that every n-connected graph with a 1-factor has at least n different 1-factors. The main purpose of this paper is to prove that every n-connected graph with a 1-factor has at least as many as n(n − 2)(n − 4) … 4 · 2, (or: n(n − 2)(n − 4) … 5 · 3) 1-factors. The main lemma used is: if a 2-connected graph G has a 1-factor, then G contains a vertex V (and even two such vertices), such that each edge of G, incident to V, belongs to some 1-factor of G. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|