✦ LIBER ✦

Toughness and the existence of k-factors. III

✍ Scribed by Hikoe Enomoto

Publisher: Elsevier Science
Year: 1998
Tongue: English
Weight: 312 KB
Volume: 189
Category: Article
ISSN: 0012-365X
DOI: 10.1016/s0012-365x(98)00059-4

No coin nor oath required. For personal study only.

✦ Synopsis

In a paper with the same title (Enomoto et al., 1985) we proved Chv&al's conjecture that ktough graphs have k-factors if they satisfy trivial necessary conditions. In this paper, we introduce a variation of toughness, and prove a stronger result for the existence of l-or 2-factors. This solves a conjecture of Liu and Yu, affirmatively. @

📜 SIMILAR VOLUMES

Toughness and the existence of k-factors

✍ Hikoe Enomoto; Bill Jackson; P. Katerinis; Akira Saito 📂 Article 📅 1985 🏛 John Wiley and Sons 🌐 English ⚖ 317 KB 👁 1 views

Toughness of graphs and the existence of

Toughness of graphs and the existence of factors

✍ P. Katerinis 📂 Article 📅 1990 🏛 Elsevier Science 🌐 English ⚖ 643 KB

## Theorem 2. Let G be a 2-tough graph. Then for any function f : V(G)+ { 1, 2) such that C xsvCcj f (x) in euen, G has an f-factor. Before stating the second main theorem of this paper it is necessary to make the following definition. Let G be a graph and let g and f be two integer-valued functi

Toughness, minimum degree, and the exist

Toughness, minimum degree, and the existence of 2-factors

✍ D. Bauer; E. Schmeichel 📂 Article 📅 1994 🏛 John Wiley and Sons 🌐 English ⚖ 690 KB

## Abstract Degree conditions on the vertices of a __t__‐tough graph __G__(1 ≦ __t__ ≦ 2) that ensure the existence of a 2‐factor in __G__ are presented. These conditions are asymptotically best possible for every __t__ ϵ [1, 3/2] and for infinitely many __t__ ϵ [3/2, 2].

A degree condition for the existence of

A degree condition for the existence of k-factors

✍ Tsuyoshi Nishimura 📂 Article 📅 1992 🏛 John Wiley and Sons 🌐 English ⚖ 358 KB 👁 1 views

## Abstract Let __k__ be an integer such that ≦, and let __G__ be a connected graph of order __n__ with ≦, __kn__ even, and minimum degree at least __k__. We prove that if __G__ satisfies max(deg(u), deg(v)) ≦ n/2 for each pair of nonadjacent vertices __u, v__ in __G__, then __G__ has a __k__‐facto

On the number of edge-disjoint one facto

On the number of edge-disjoint one factors and the existence of k-factors in complete multipartite graphs

✍ D.G. Hoffman; C.A. Rodger 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 503 KB

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 Erd6s-Gallai conditions for the existence of simple

The existence of Ck-factorizations of K2

The existence of Ck-factorizations of K2n − F

✍ D.G. Hoffman; P.J. Schellenberg 📂 Article 📅 1991 🏛 Elsevier Science 🌐 English ⚖ 414 KB

A necessary condition for the existence of a C,-factorization of KZn -F is that k divides 2n. It is known that neither K, -F nor K,, -F admit a C,-factorization. In this paper we show that except for these two cases, the necessary condition is also sufficient.