Previous |  Up |  Next


Title: Minimal claw-free graphs (English)
Author: Dankelmann, P.
Author: Swart, Henda C.
Author: van den Berg, P.
Author: Goddard, W.
Author: Plummer, M. D.
Language: English
Journal: Czechoslovak Mathematical Journal
ISSN: 0011-4642 (print)
ISSN: 1572-9141 (online)
Volume: 58
Issue: 3
Year: 2008
Pages: 787-798
Summary lang: English
Category: math
Summary: 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. (English)
Keyword: minimal claw-free
Keyword: degree
Keyword: bow-tie
Keyword: line graph
MSC: 05C07
MSC: 05C75
idZBL: Zbl 1174.05107
idMR: MR2455938
Date available: 2010-07-20T14:07:39Z
Last updated: 2016-04-07
Stable URL:
Reference: [1] Chartrand, G., Lesniak, L.: Graphs & Digraphs.Third edition, Chapman and Hall, London (1996). Zbl 0890.05001, MR 1408678
Reference: [2] Chudnovsky, M., Seymour, P.: The structure of claw-free graphs.Surveys in combinatorics (2005), 153-171 London Math. Soc. Lecture Note Ser., 327, Cambridge Univ. Press (2005). Zbl 1109.05092, MR 2187738
Reference: [3] Faudree, R., Flandrin, E., Ryjáček, Z.: Claw-free graphs---a survey.Discrete Math. 164 (1997), 87-147. MR 1432221, 10.1016/S0012-365X(96)00045-3
Reference: [4] Plummer, M. D.: A note on Hamilton cycles in claw-free graphs.Congr. Numer. 96 (1993), 113-122. Zbl 0801.05048, MR 1267307
Reference: [5] Plummer, M. D.: Extending matchings in claw-free graphs.Discrete Math. 125 (1994), 301-307. Zbl 0798.05041, MR 1263759, 10.1016/0012-365X(94)90171-6
Reference: [6] Ryjáček, Z.: On a closure concept in claw-free graphs.J. Combin. Theory Ser. B 70 (1997), 217-224. MR 1459867, 10.1006/jctb.1996.1732
Reference: [7] Sedláček, J.: Some properties of interchange graphs.1964 Theory of Graphs and its Applications, Academic Press, Prague 145-150. MR 0173255
Reference: [8] Sumner, D. P.: Minimal line graphs.Glasgow Math. J. 17 (1976), 12-16. Zbl 0328.05132, MR 0409272, 10.1017/S0017089500002652
Reference: [9] Rooij, A. C. M. van, Wilf, H. S.: The interchange graph of a finite graph.Acta Math. Acad. Sci. Hungar. 16 (1965), 263-269. MR 0195761, 10.1007/BF01904834


Files Size Format View
CzechMathJ_58-2008-3_15.pdf 235.3Kb application/pdf View/Open
Back to standard record
Partner of
EuDML logo