A Degree Condition for the Existence of Regular Factors in K1, n-Free Graphs

Katsuhiro Ota; Taro Tokuda

doi:10.1002/(SICI)1097-0118(199605)22:1<59::AID-JGT8>3.0.CO;2-K

A Degree Condition for the Existence of Regular Factors in K₁, _n-Free Graphs

Katsuhiro Ota
, Taro Tokuda

Department of Mathematics

Research output: Contribution to journal › Article › peer-review

22 Citations (Scopus)

Abstract

A graph is called K₁, _n-free if it contains no K₁, _n as an induced subgraph. Let n(≥ 3), r be integers (if r is odd, r ≥ n - 1). We prove that every K₁, _n-free connected graph G with r|V(G)| even has an r-factor if its minimum degree is at least (n + n-1/r) ⌈n/2(n - 1) r⌉ - n - 1/r (⌈n/2(n - 1) r⌉)² + n - 3. This degree condition is sharp.

Original language	English
Pages (from-to)	59-64
Number of pages	6
Journal	Journal of Graph Theory
Volume	22
Issue number	1
DOIs	https://doi.org/10.1002/(SICI)1097-0118(199605)22:1<59::AID-JGT8>3.0.CO;2-K
Publication status	Published - 1996 May

ASJC Scopus subject areas

Geometry and Topology
Discrete Mathematics and Combinatorics

Access to Document

10.1002/(SICI)1097-0118(199605)22:1<59::AID-JGT8>3.0.CO;2-K

Cite this

@article{2a7d784f65d14e31b8884329b5c9ccd3,

title = "A Degree Condition for the Existence of Regular Factors in K1, n-Free Graphs",

abstract = "A graph is called K1, n-free if it contains no K1, n as an induced subgraph. Let n(≥ 3), r be integers (if r is odd, r ≥ n - 1). We prove that every K1, n-free connected graph G with r|V(G)| even has an r-factor if its minimum degree is at least (n + n-1/r) ⌈n/2(n - 1) r⌉ - n - 1/r (⌈n/2(n - 1) r⌉)2 + n - 3. This degree condition is sharp.",

author = "Katsuhiro Ota and Taro Tokuda",

year = "1996",

month = may,

doi = "10.1002/(SICI)1097-0118(199605)22:1<59::AID-JGT8>3.0.CO;2-K",

language = "English",

volume = "22",

pages = "59--64",

journal = "Journal of Graph Theory",

issn = "0364-9024",

publisher = "Wiley-Liss Inc.",

number = "1",

}

TY - JOUR

T1 - A Degree Condition for the Existence of Regular Factors in K1, n-Free Graphs

AU - Ota, Katsuhiro

AU - Tokuda, Taro

PY - 1996/5

Y1 - 1996/5

N2 - A graph is called K1, n-free if it contains no K1, n as an induced subgraph. Let n(≥ 3), r be integers (if r is odd, r ≥ n - 1). We prove that every K1, n-free connected graph G with r|V(G)| even has an r-factor if its minimum degree is at least (n + n-1/r) ⌈n/2(n - 1) r⌉ - n - 1/r (⌈n/2(n - 1) r⌉)2 + n - 3. This degree condition is sharp.

AB - A graph is called K1, n-free if it contains no K1, n as an induced subgraph. Let n(≥ 3), r be integers (if r is odd, r ≥ n - 1). We prove that every K1, n-free connected graph G with r|V(G)| even has an r-factor if its minimum degree is at least (n + n-1/r) ⌈n/2(n - 1) r⌉ - n - 1/r (⌈n/2(n - 1) r⌉)2 + n - 3. This degree condition is sharp.

UR - https://www.scopus.com/pages/publications/0030551098

UR - https://www.scopus.com/pages/publications/0030551098#tab=citedBy

U2 - 10.1002/(SICI)1097-0118(199605)22:1<59::AID-JGT8>3.0.CO;2-K

DO - 10.1002/(SICI)1097-0118(199605)22:1<59::AID-JGT8>3.0.CO;2-K

M3 - Article

AN - SCOPUS:0030551098

SN - 0364-9024

VL - 22

SP - 59

EP - 64

JO - Journal of Graph Theory

JF - Journal of Graph Theory

IS - 1

ER -

A Degree Condition for the Existence of Regular Factors in K₁, _n-Free Graphs

Abstract

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this