×

Minimal claw-free graphs. (English) Zbl 1174.05107

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.

MSC:

05C75 Structural characterization of families of graphs
05C07 Vertex degrees
PDFBibTeX XMLCite
Full Text: DOI EuDML

References:

[1] G. Chartrand and L. Lesniak: Graphs & Digraphs. Third edition, Chapman and Hall, London, 1996.
[2] M. Chudnovsky and P. Seymour: 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
[3] R. Faudree, E. Flandrin and Z. Ryjáček: Claw-free graphs–a survey. Discrete Math. 164 (1997), 87–147. · Zbl 0879.05043 · doi:10.1016/S0012-365X(96)00045-3
[4] M. D. Plummer: A note on Hamilton cycles in claw-free graphs. Congr. Numer. 96 (1993), 113–122. · Zbl 0801.05048
[5] M. D. Plummer: Extending matchings in claw-free graphs. Discrete Math. 125 (1994), 301–307. · Zbl 0798.05041 · doi:10.1016/0012-365X(94)90171-6
[6] Z. Ryjáček: On a closure concept in claw-free graphs. J. Combin. Theory Ser. B 70 (1997), 217–224. · Zbl 0872.05032 · doi:10.1006/jctb.1996.1732
[7] J. Sedláček: Some properties of interchange graphs. 1964 Theory of Graphs and its Applications, Academic Press, Prague, pp. 145–150.
[8] D. P. Sumner: Minimal line graphs. Glasgow Math. J. 17 (1976), 12–16. · Zbl 0328.05132 · doi:10.1017/S0017089500002652
[9] A. C. M. van Rooij and H. S. Wilf: The interchange graph of a finite graph. Acta Math. Acad. Sci. Hungar. 16 (1965), 263–269. · Zbl 0139.17203 · doi:10.1007/BF01904834
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.