✦ LIBER ✦

A degree condition for the existence of k-factors

✍ Scribed by Tsuyoshi Nishimura

Publisher: John Wiley and Sons
Year: 1992
Tongue: English
Weight: 358 KB
Volume: 16
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.3190160205

No coin nor oath required. For personal study only.

✦ Synopsis

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‐factor.

📜 SIMILAR VOLUMES

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.

Ore-type condition for the existence of

Ore-type condition for the existence of connected factors

✍ Yunsun Nam 📂 Article 📅 2007 🏛 John Wiley and Sons 🌐 English ⚖ 130 KB

## Abstract In this article, we obtain some Ore‐type sufficient conditions for a graph to have a connected factor with degree restrictions. Let α and __k__ be positive integers with $\alpha \ge {{k + 1} \over{k - 1}}$ if ${{k}} \ge 2$ and $\alpha \ge 4$ if ${{k}}=1$. Let __G__ be a connected graph

Some conditions for the existence of f-f

Some conditions for the existence of f-factors

✍ P. Katerinis 📂 Article 📅 1985 🏛 John Wiley and Sons 🌐 English ⚖ 268 KB 👁 1 views

Let m, 1, n be three odd integers such that m < I < n. It is proved that if a graph G has an mfactor and an rrfactor, then it also has an /factor. In addition, we obtain sufficient conditions for the existence of an f-factor, in terms of vertexdeleted subgraphs. All graphs considered here are multi

A degree condition for a graph to have [

A degree condition for a graph to have [a,b]-factors

✍ Li, Yanjun; Mao-cheng, Cai 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 131 KB 👁 2 views

Let G be a graph of order n, and let a and b be integers such that a+b for any two nonadjacent vertices u and v in G. This result is best possible, and it is an extension of T. Iida and T. Nishimura's results (T. Iida and T. Nishimura, An Ore-type condition for the existence of k-factors in graphs,

Some sufficient conditions for the exist

Some sufficient conditions for the existence of a 1-factor

✍ Ladislav Nebeský 📂 Article 📅 1978 🏛 John Wiley and Sons 🌐 English ⚖ 208 KB 👁 1 views

## Abstract The following theorem is proved: Let __G__ be a graph of even order. Assume that there exists a connected spanning subgraph __F__ of __G__ such that for every set __U__ of four vertices in __G__, if the subgraph of __F__ induced by __U__ is a star, then the subgraph of __G__ induced by

A Degree Sum Condition for the Existence

A Degree Sum Condition for the Existence of a Contractible Edge in a κ-Connected Graph

✍ Matthias Kriesell 📂 Article 📅 2001 🏛 Elsevier Science 🌐 English ⚖ 184 KB

It is known that a noncomplete }-connected graph of minimum degree of at least w 5} 4 x contains a }-contractible edge, i.e., an edge whose contraction yields again a }-connected graph. Here we prove the stronger statement that a noncomplete }-connected graph for which the sum of the degrees of any