𝔖 Bobbio Scriptorium
✦   LIBER   ✦

A Chvátal-Erdös condition for (1,1)-factors in digraphs

✍ Scribed by Bill Jackson; Oscat Ordaz

Publisher
Elsevier Science
Year
1985
Tongue
English
Weight
171 KB
Volume
57
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

✦ Synopsis

We show that if the independence number of a k-connected digraph D is at most k, then D has a spanning subgraph which consists of a union of vertex-disjoint directed circuits. As a corollary we determine the minimum number of edges required in a k-connected oriented graph to ensure the existence of such a subgraph.

📜 SIMILAR VOLUMES

A Chvátal-Erdös condition for (t, t)-fac
A Chvátal-Erdös condition for (t, t)-factors in digraphs using given arcs
✍ Pierre Fraisse; Oscar Ordaz 📂 Article 📅 1988 🏛 Elsevier Science 🌐 English ⚖ 570 KB

Let D b a k-connected digraph with independence number (Y. We show that for any integers t and p such that k 3 $ti (t + 1) i-p, then any set of arcs of cardinal@ p inducing a subgraph with maximum in-and outdegree at most t is contained in a spanning subgraph which is regular of in-and out-degree t,

A 2-factor with two components of a grap
A 2-factor with two components of a graph satisfying the Chvátal-Erdös condition
✍ Atsushi Kaneko; Kiyoshi Yoshimoto 📂 Article 📅 2003 🏛 John Wiley and Sons 🌐 English ⚖ 142 KB 👁 1 views

## Abstract Chvátal and Erdös showed that a __k__‐connected graph with independence number at most __k__ and order at least three is hamiltonian. In this paper, we show that a graph contains a 2‐factor with two components, i.e., the graph can be divided into two cycles if the graph is __k__(≥ 4)‐co

Chvátal-Erdős conditions for pat
Chvátal-Erdős conditions for paths and cycles in graphs and digraphs. A survey
✍ Bill Jackson; Oscar Ordaz 📂 Article 📅 1990 🏛 Elsevier Science 🌐 English ⚖ 783 KB

We give a survey of results and conjectures concerning sufficient conditions in terms of connectivity and independence number for which a graph or digraph has various path or cyclic properties, for example hamilton path/cycle, hamilton connected, pancyclic, path/cycle covers, 2-cyclic.

A sufficient condition for a graph to co
A sufficient condition for a graph to contain three disjoint 1-factors
✍ Sein Win 📂 Article 📅 1982 🏛 John Wiley and Sons 🌐 English ⚖ 219 KB 👁 1 views

## Abstract Ore derived a sufficient condition for a graph to contain a Hamiltonian cycle. We obtain a sufficient condition, similar to Ore's condition, for a graph to contain a Hamiltonian cycle and a 1‐factor which are edge disjoint.

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.