Geodesic
Minimal claw-free graphs
Czechoslovak Mathematical Journal, Tome 58 (2008) no. 3, pp. 787-798 Cet article a éte moissonné depuis la source Czech Digital Mathematics Library

Voir la notice de l'article

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.
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.
Classification : 05C07, 05C75
Keywords: minimal claw-free; degree; bow-tie; line graph 
@article{CMJ_2008_58_3_a14,
     author = {Dankelmann, P. and Swart, Henda C. and van den Berg, P. and Goddard, W. and Plummer, M. D.},
     title = {Minimal claw-free graphs},
     journal = {Czechoslovak Mathematical Journal},
     pages = {787--798},
     year = {2008},
     volume = {58},
     number = {3},
     mrnumber = {2455938},
     zbl = {1174.05107},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/CMJ_2008_58_3_a14/}
}
TY  - JOUR
AU  - Dankelmann, P.
AU  - Swart, Henda C.
AU  - van den Berg, P.
AU  - Goddard, W.
AU  - Plummer, M. D.
TI  - Minimal claw-free graphs
JO  - Czechoslovak Mathematical Journal
PY  - 2008
SP  - 787
EP  - 798
VL  - 58
IS  - 3
UR  - http://geodesic.mathdoc.fr/item/CMJ_2008_58_3_a14/
LA  - en
ID  - CMJ_2008_58_3_a14
ER  - 
%0 Journal Article
%A Dankelmann, P.
%A Swart, Henda C.
%A van den Berg, P.
%A Goddard, W.
%A Plummer, M. D.
%T Minimal claw-free graphs
%J Czechoslovak Mathematical Journal
%D 2008
%P 787-798
%V 58
%N 3
%U http://geodesic.mathdoc.fr/item/CMJ_2008_58_3_a14/
%G en
%F CMJ_2008_58_3_a14
Dankelmann, P.; Swart, Henda C.; van den Berg, P.; Goddard, W.; Plummer, M. D. Minimal claw-free graphs. Czechoslovak Mathematical Journal, Tome 58 (2008) no. 3, pp. 787-798. http://geodesic.mathdoc.fr/item/CMJ_2008_58_3_a14/

[1] Chartrand, G., Lesniak, L.: Graphs & Digraphs. Third edition, Chapman and Hall, London (1996). | MR | Zbl

[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). | MR | Zbl

[3] Faudree, R., Flandrin, E., Ryjáček, Z.: Claw-free graphs---a survey. Discrete Math. 164 (1997), 87-147. | DOI | MR

[4] Plummer, M. D.: A note on Hamilton cycles in claw-free graphs. Congr. Numer. 96 (1993), 113-122. | MR | Zbl

[5] Plummer, M. D.: Extending matchings in claw-free graphs. Discrete Math. 125 (1994), 301-307. | DOI | MR | Zbl

[6] Ryjáček, Z.: On a closure concept in claw-free graphs. J. Combin. Theory Ser. B 70 (1997), 217-224. | DOI | MR

[7] Sedláček, J.: Some properties of interchange graphs. 1964 Theory of Graphs and its Applications, Academic Press, Prague 145-150. | MR

[8] Sumner, D. P.: Minimal line graphs. Glasgow Math. J. 17 (1976), 12-16. | DOI | MR | Zbl

[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. | DOI | MR