Minimal claw-free graphs

P. Dankelmann; Henda C. Swart; P. Van Den Berg; W. Goddard; M. D. Plummer

doi:10.1007/s10587-008-0051-6

Minimal claw-free graphs

P. Dankelmann, Henda C. Swart, P. Van Den Berg, W. Goddard, M. D. Plummer

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

Abstract

A graph G is a minimal claw-free graph (m.c.f. graph) if it contains no K_1,3 (claw) as an induced subgraph and if, for each edge e of G, G ™ e contains an induced claw. We investigate properties of m.c.f. graphs, establish sharp bounds on their orders and the degrees of their vertices, and characterize graphs which have m.c.f. line graphs.

Original language	English
Pages (from-to)	787-798
Number of pages	12
Journal	Czechoslovak Mathematical Journal
Volume	58
Issue number	3
DOIs	https://doi.org/10.1007/s10587-008-0051-6
Publication status	Published - Sept 2008
Externally published	Yes

Keywords

Bow-tie
Degree
Line graph
Minimal claw-free

ASJC Scopus subject areas

General Mathematics

Access to Document

10.1007/s10587-008-0051-6

Cite this

@article{ce2020a0c0764c2c9f7b8153335699d9,

title = "Minimal claw-free graphs",

abstract = "A graph G is a minimal claw-free graph (m.c.f. graph) if it contains no K1,3 (claw) as an induced subgraph and if, for each edge e of G, G {\texttrademark} e contains an induced claw. We investigate properties of m.c.f. graphs, establish sharp bounds on their orders and the degrees of their vertices, and characterize graphs which have m.c.f. line graphs.",

keywords = "Bow-tie, Degree, Line graph, Minimal claw-free",

author = "P. Dankelmann and Swart, {Henda C.} and {Van Den Berg}, P. and W. Goddard and Plummer, {M. D.}",

year = "2008",

month = sep,

doi = "10.1007/s10587-008-0051-6",

language = "English",

volume = "58",

pages = "787--798",

journal = "Czechoslovak Mathematical Journal",

issn = "0011-4642",

publisher = "Springer New York",

number = "3",

}

TY - JOUR

T1 - Minimal claw-free graphs

AU - Dankelmann, P.

AU - Swart, Henda C.

AU - Van Den Berg, P.

AU - Goddard, W.

AU - Plummer, M. D.

PY - 2008/9

Y1 - 2008/9

N2 - A graph G is a minimal claw-free graph (m.c.f. graph) if it contains no K1,3 (claw) as an induced subgraph and if, for each edge e of G, G ™ e contains an induced claw. We investigate properties of m.c.f. graphs, establish sharp bounds on their orders and the degrees of their vertices, and characterize graphs which have m.c.f. line graphs.

AB - A graph G is a minimal claw-free graph (m.c.f. graph) if it contains no K1,3 (claw) as an induced subgraph and if, for each edge e of G, G ™ e contains an induced claw. We investigate properties of m.c.f. graphs, establish sharp bounds on their orders and the degrees of their vertices, and characterize graphs which have m.c.f. line graphs.

KW - Bow-tie

KW - Degree

KW - Line graph

KW - Minimal claw-free

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

U2 - 10.1007/s10587-008-0051-6

DO - 10.1007/s10587-008-0051-6

M3 - Article

AN - SCOPUS:67149120815

SN - 0011-4642

VL - 58

SP - 787

EP - 798

JO - Czechoslovak Mathematical Journal

JF - Czechoslovak Mathematical Journal

IS - 3

ER -

Minimal claw-free graphs

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this