✦ LIBER ✦

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

✍ Scribed by D. Bauer; E. Schmeichel

Publisher: John Wiley and Sons
Year: 1994
Tongue: English
Weight: 690 KB
Volume: 18
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.3190180304

No coin nor oath required. For personal study only.

✦ Synopsis

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

📜 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 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

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

A degree condition for the existence of

A degree condition for the existence of regular factors inK1,n-free graphs

✍ Ota, Katsuhiro; Tokuda, Taro 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 260 KB 👁 2 views

A graph is called K1,.-free if it contains no K l , n as an induced subgraph. Let n ( r 3), r be integers (if r is odd, r 2 n -1). We prove that every Kl,,-free connected graph G with rlV(G)I even has an r-factor if its minimum degree is at least This degree condition is sharp.

The minimum degree of Ramsey-minimal gra

The minimum degree of Ramsey-minimal graphs

✍ Jacob Fox; Kathy Lin 📂 Article 📅 2006 🏛 John Wiley and Sons 🌐 English ⚖ 144 KB 👁 1 views

## Abstract We write __H__ → __G__ if every 2‐coloring of the edges of graph __H__ contains a monochromatic copy of graph __G__. A graph __H__ is __G__‐__minimal__ if __H__ → __G__, but for every proper subgraph __H__′ of __H__, __H__′ ↛ __G__. We define __s__(__G__) to be the minimum __s__ such th