| 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:
|
2020-07-03 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/140421 |
| . |
| 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 |
| . |
