✦ LIBER ✦

Stability number and [a,b]-factors in graphs

✍ Scribed by Mekkia Kouider; Zbigniew Lonc

Publisher: John Wiley and Sons
Year: 2004
Tongue: English
Weight: 90 KB
Volume: 46
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.20008

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

A spanning subgraph whose vertices have degrees belonging to the interval [a,b], where a and b are positive integers, such that a ≤ b, is called an [a,b]‐factor. In this paper, we prove sufficient conditions for existence of an [a,b]‐factor, a connected [a,b]‐factor, and a 2‐connected [a,b]‐factor. The conditions involve the minimum degree, the stability number, and the connectivity of a graph. © 2004 Wiley Periodicals, Inc. J Graph Theory 46: 254–264, 2004

📜 SIMILAR VOLUMES

Cycles in Graphs with Prescribed Stabili

Cycles in Graphs with Prescribed Stability Number and Connectivity

✍ M. Kouider 📂 Article 📅 1994 🏛 Elsevier Science 🌐 English ⚖ 113 KB

Restricted b-factors in bipartite graphs

Restricted b-factors in bipartite graphs and t-designs

✍ Ivette Arámbula; Illya V. Hicks 📂 Article 📅 2006 🏛 John Wiley and Sons 🌐 English ⚖ 178 KB

## Abstract We present a new equivalence result between restricted __b__‐factors in bipartite graphs and combinatorial __t__‐designs. This result is useful in the construction of __t__‐designs by polyhedral methods. We propose a novel linear integer programming formulation, which we call GDP, for t

Scattering number in graphs

✍ Shenggui Zhang; Ziguo Wang 📂 Article 📅 2001 🏛 John Wiley and Sons 🌐 English ⚖ 75 KB 👁 1 views

Stability, domination and irredundance i

Stability, domination and irredundance in a graph

✍ Odile Favaron 📂 Article 📅 1986 🏛 John Wiley and Sons 🌐 English ⚖ 441 KB

In a graph G, a set X is called a stable set if any two vertices of X are nonadjacent. A set X is called a dominating set if every vertex of V-X is joined to at least one vertex of X. A set Xis called an irredundant set if every vertex of X, not isolated in X, has at least one proper neighbor, that

Sharp bounds on the order, size, and sta

Sharp bounds on the order, size, and stability number of graphs

✍ Pierre Hansen; Maolin Zheng 📂 Article 📅 1993 🏛 John Wiley and Sons 🌐 English ⚖ 276 KB

## Abstract We consider graphs __G = (V,E)__ with order ρ = |__V__|, size __e__ = |__E__|, and stability number β~0~. We collect or determine upper and lower bounds on each of these parameters expressed as functions of the two others. We prove that all these bounds are sharp. © __1993 by John Wiley

Hamiltonian ?-factors in graphs

✍ Wei, Bing; Zhu, Yongjin 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 128 KB 👁 2 views

Let k ≥ 2 be an integer. A k-factor F of a graph G is called a hamiltonian k-factor if F contains a hamiltonian cycle. In this paper, we shall prove that if G is a graph of order n with k ≥ 2, n ≥ 8k -4, kn even and δ(G) ≥ n/2, then G has a hamiltonian k-factor.