An ore-type condition for the existence of k-factors in graphs

Tadashi Iida; Tsuyoshi Nishimura

doi:10.1007/BF01787640

An ore-type condition for the existence of k-factors in graphs

Tadashi Iida, Tsuyoshi Nishimura

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

29 Citations (Scopus)

Abstract

Let k be a positive integer, and let G be a graph of order n with n ≧ 4 k - 5, kn even and minimum degree at least k. We prove that if the degree sum of each pair of nonadjacent vertices is at least n, then G has a k-factor.

Original language	English
Pages (from-to)	353-361
Number of pages	9
Journal	Graphs and Combinatorics
Volume	7
Issue number	4
DOIs	https://doi.org/10.1007/BF01787640
Publication status	Published - 1991 Dec 1
Externally published	Yes

ASJC Scopus subject areas

Theoretical Computer Science
Discrete Mathematics and Combinatorics

Access to Document

10.1007/BF01787640

Cite this

@article{716f5e750c1e43b78ed541fe85c0cc4e,

title = "An ore-type condition for the existence of k-factors in graphs",

abstract = "Let k be a positive integer, and let G be a graph of order n with n ≧ 4 k - 5, kn even and minimum degree at least k. We prove that if the degree sum of each pair of nonadjacent vertices is at least n, then G has a k-factor.",

author = "Tadashi Iida and Tsuyoshi Nishimura",

year = "1991",

month = dec,

day = "1",

doi = "10.1007/BF01787640",

language = "English",

volume = "7",

pages = "353--361",

journal = "Graphs and Combinatorics",

issn = "0911-0119",

publisher = "Springer Japan",

number = "4",

}

TY - JOUR

T1 - An ore-type condition for the existence of k-factors in graphs

AU - Iida, Tadashi

AU - Nishimura, Tsuyoshi

PY - 1991/12/1

Y1 - 1991/12/1

N2 - Let k be a positive integer, and let G be a graph of order n with n ≧ 4 k - 5, kn even and minimum degree at least k. We prove that if the degree sum of each pair of nonadjacent vertices is at least n, then G has a k-factor.

AB - Let k be a positive integer, and let G be a graph of order n with n ≧ 4 k - 5, kn even and minimum degree at least k. We prove that if the degree sum of each pair of nonadjacent vertices is at least n, then G has a k-factor.

UR - http://www.scopus.com/inward/record.url?scp=0039754882&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0039754882&partnerID=8YFLogxK

U2 - 10.1007/BF01787640

DO - 10.1007/BF01787640

M3 - Article

AN - SCOPUS:0039754882

SN - 0911-0119

VL - 7

SP - 353

EP - 361

JO - Graphs and Combinatorics

JF - Graphs and Combinatorics

IS - 4

ER -

An ore-type condition for the existence of k-factors in graphs

Abstract

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this