𝔖 Bobbio Scriptorium
✦   LIBER   ✦

K4−-factor in a graph

✍ Scribed by Ken-ichi Kawarabayashi

Publisher
John Wiley and Sons
Year
2002
Tongue
English
Weight
194 KB
Volume
39
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

Let G be a graph of order 4__k__ and let δ(G) denote the minimum degree of G. Let F be a given connected graph. Suppose that |V(G)| is a multiple of |V(F)|. A spanning subgraph of G is called an F‐factor if its components are all isomorphic to F.

In this paper, we prove that if δ(G)≥5/2__k__, then G contains a K~4~^−^‐factor (K~4~^−^ is the graph obtained from K~4~ by deleting just one edge). The condition on the minimum degree is best possible in a sense. In addition, the proof can be made algorithmic. © 2002 John Wiley & Sons, Inc. J Graph Theory 39: 111–128, 2002

📜 SIMILAR VOLUMES

Regular factors in K1,3-free graphs
Regular factors in K1,3-free graphs
✍ S. A. Choudum; M. S. Paulraj 📂 Article 📅 1991 🏛 John Wiley and Sons 🌐 English ⚖ 247 KB 👁 1 views

## Abstract We show that every connected __K__~1,3~‐free graph with minimum degree at least __2k__ contains a __k__‐factor and construct connected __K__~1,3~‐free graphs with minimum degree __k__ + __0__(√__k__) that have no __k__‐factor.

Regular factors in K1,n free graphs
Regular factors in K1,n free graphs
✍ Yoshimi Egawa; Katsuhiro Ota 📂 Article 📅 1991 🏛 John Wiley and Sons 🌐 English ⚖ 280 KB

## Abstract A graph is said to be __K__~1,__n__~‐free, if it contains no __K__~1,__n__~ as an induced subgraph. We prove that for __n__ ⩾ 3 and __r__ ⩾ __n__ −1, if __G__ is a __K__~1,__n__~‐free graph with minimum degree at least (__n__^2^/4(__n__ −1))__r__ + (3__n__ −6)/2 + (__n__ −1)/4__r__, the

The virtual k-factorability of graphs
The virtual k-factorability of graphs
✍ Seiya Negami 📂 Article 📅 1987 🏛 John Wiley and Sons 🌐 English ⚖ 340 KB

It is shown that if a connected graph G admits a finite covering that has a k-factor, then there is a 1 -or 2-fold covering of G that has a k-factor and that such a covering can be given as a canonical bipartite graph associated with G. will conflict with the first one in Czn-, but there is no trou

Domination in a graph with a 2-factor
Domination in a graph with a 2-factor
✍ Ken-ichi Kawarabayashi; Michael D. Plummer; Akira Saito 📂 Article 📅 2006 🏛 John Wiley and Sons 🌐 English ⚖ 77 KB

## Abstract Let γ(__G__) be the domination number of a graph __G__. Reed 6 proved that every graph __G__ of minimum degree at least three satisfies γ(__G__) ≤ (3/8)|__G__|, and conjectured that a better upper bound can be obtained for cubic graphs. In this paper, we prove that a 2‐edge‐connected cu