Two forbidden subgraphs and the existence of a 2-factor In graphs

R. E.L. Aldred; Jun Fujisawa; Akira Saito

Two forbidden subgraphs and the existence of a 2-factor In graphs

R. E.L. Aldred, Jun Fujisawa, Akira Saito

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

Abstract

In 1996, Ota and Tokuda showed that a star-free graph with sufficiently high minimum degree admits a 2-factor. More recently it was shown that the minimum degree condition can be significantly reduced if one also requires that the graph is not only star-free but also of sufficiently high edge-connectivity. In this paper we reduce the minimum degree condition further for star-free graphs that also avoid W M_r, where W M_r is the graph K₁ + _rK₂.

Original language	English
Pages (from-to)	235-246
Number of pages	12
Journal	Australasian Journal of Combinatorics
Volume	44
Publication status	Published - 2009 Jun 1
Externally published	Yes

ASJC Scopus subject areas

Discrete Mathematics and Combinatorics

Cite this

@article{472c708ea8784317b9bd27055f8fd360,

title = "Two forbidden subgraphs and the existence of a 2-factor In graphs",

abstract = "In 1996, Ota and Tokuda showed that a star-free graph with sufficiently high minimum degree admits a 2-factor. More recently it was shown that the minimum degree condition can be significantly reduced if one also requires that the graph is not only star-free but also of sufficiently high edge-connectivity. In this paper we reduce the minimum degree condition further for star-free graphs that also avoid W Mr, where W Mr is the graph K1 + rK2.",

author = "Aldred, {R. E.L.} and Jun Fujisawa and Akira Saito",

year = "2009",

month = jun,

day = "1",

language = "English",

volume = "44",

pages = "235--246",

journal = "Australasian Journal of Combinatorics",

issn = "1034-4942",

publisher = "University of Queensland Press",

}

TY - JOUR

T1 - Two forbidden subgraphs and the existence of a 2-factor In graphs

AU - Aldred, R. E.L.

AU - Fujisawa, Jun

AU - Saito, Akira

PY - 2009/6/1

Y1 - 2009/6/1

N2 - In 1996, Ota and Tokuda showed that a star-free graph with sufficiently high minimum degree admits a 2-factor. More recently it was shown that the minimum degree condition can be significantly reduced if one also requires that the graph is not only star-free but also of sufficiently high edge-connectivity. In this paper we reduce the minimum degree condition further for star-free graphs that also avoid W Mr, where W Mr is the graph K1 + rK2.

AB - In 1996, Ota and Tokuda showed that a star-free graph with sufficiently high minimum degree admits a 2-factor. More recently it was shown that the minimum degree condition can be significantly reduced if one also requires that the graph is not only star-free but also of sufficiently high edge-connectivity. In this paper we reduce the minimum degree condition further for star-free graphs that also avoid W Mr, where W Mr is the graph K1 + rK2.

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

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

M3 - Article

AN - SCOPUS:67449115795

SN - 1034-4942

VL - 44

SP - 235

EP - 246

JO - Australasian Journal of Combinatorics

JF - Australasian Journal of Combinatorics

ER -

Two forbidden subgraphs and the existence of a 2-factor In graphs

Abstract

ASJC Scopus subject areas

Other files and links

Fingerprint

Cite this