Toughness and the existence of fractional k-factors of graphs |
| |
Authors: | Guizhen Liu Lanju Zhang |
| |
Institution: | a School of Mathematics and System Science, Shandong University, Jinan 250100, PR China b Biostatistics and Data Management, Medimmune Inc., Gaithersburg, MD 20878, USA |
| |
Abstract: | The toughness of a graph G, t(G), is defined as t(G)=min{|S|/ω(G-S)|S⊆V(G),ω(G-S)>1} where ω(G-S) denotes the number of components of G-S or t(G)=+∞ if G is a complete graph. Much work has been contributed to the relations between toughness and the existence of factors of a graph. In this paper, we consider the relationship between the toughness and the existence of fractional k-factors. It is proved that a graph G has a fractional 1-factor if t(G)?1 and has a fractional k-factor if t(G)?k-1/k where k?2. Furthermore, we show that both results are best possible in some sense. |
| |
Keywords: | 05C70 |
本文献已被 ScienceDirect 等数据库收录! |
|