✦ LIBER ✦

Toughness of graphs and the existence of factors

✍ Scribed by P. Katerinis

Publisher: Elsevier Science
Year: 1990
Tongue: English
Weight: 643 KB
Volume: 80
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(90)90297-u

No coin nor oath required. For personal study only.

✦ Synopsis

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 functions defined on

such that g(x) Sf (x) f or all x E V(G). Then a [g, f]-factor of G is a

📜 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 and the existence of k-factors

Toughness and the existence of k-factors. III

✍ Hikoe Enomoto 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 312 KB

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 con

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].

Edge-chromatic critical graphs and the e

Edge-chromatic critical graphs and the existence of 1-factors

✍ S. A. Choudum 📂 Article 📅 1993 🏛 John Wiley and Sons 🌐 English ⚖ 300 KB 👁 1 views

## Abstract We give examples of edge‐chromatic critical graphs __G__ of the following types: (i) of even order and having no 1‐factor, and (ii) of odd order and having a vertex __v__ of minimum degree such that __G__ − __v__ has no 1‐factor. The first disproves a conjecture of S. Fiorini and R. J.

The toughness of split graphs

✍ Gerhard J. Woeginger 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 117 KB

In this short note we argue that the toughness of split graphs can be computed in polynomial time.

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