Article
Full entry |
PDF
(0.2 MB)
Feedback
PDF
(0.2 MB)
Feedback
Keywords:
minimal claw-free; degree; bow-tie; line graph
minimal claw-free; degree; bow-tie; line graph
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.
References:
[1] Chartrand, G., Lesniak, L.: Graphs & Digraphs. Third edition, Chapman and Hall, London (1996). MR 1408678 | Zbl 0890.05001
[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 2187738 | Zbl 1109.05092
[3] Faudree, R., Flandrin, E., Ryjáček, Z.: Claw-free graphs---a survey. Discrete Math. 164 (1997), 87-147. DOI 10.1016/S0012-365X(96)00045-3 | MR 1432221
[4] Plummer, M. D.: A note on Hamilton cycles in claw-free graphs. Congr. Numer. 96 (1993), 113-122. MR 1267307 | Zbl 0801.05048
[5] Plummer, M. D.: Extending matchings in claw-free graphs. Discrete Math. 125 (1994), 301-307. DOI 10.1016/0012-365X(94)90171-6 | MR 1263759 | Zbl 0798.05041
[6] Ryjáček, Z.: On a closure concept in claw-free graphs. J. Combin. Theory Ser. B 70 (1997), 217-224. DOI 10.1006/jctb.1996.1732 | MR 1459867
[7] Sedláček, J.: Some properties of interchange graphs. 1964 Theory of Graphs and its Applications, Academic Press, Prague 145-150. MR 0173255
[8] Sumner, D. P.: Minimal line graphs. Glasgow Math. J. 17 (1976), 12-16. DOI 10.1017/S0017089500002652 | MR 0409272 | Zbl 0328.05132
[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 10.1007/BF01904834 | MR 0195761
Search
Partner of
