Minimal claw-free graphs
P. Dankelmann; Henda C. Swart; P. van den Berg; Wayne Goddard; M. D. Plummer
Czechoslovak Mathematical Journal (2008)
- Volume: 58, Issue: 3, page 787-798
- ISSN: 0011-4642
Access Full Article
top
Abstract
topHow to cite
topDankelmann, P., et al. "Minimal claw-free graphs." Czechoslovak Mathematical Journal 58.3 (2008): 787-798. <http://eudml.org/doc/37868>.
@article{Dankelmann2008,
abstract = {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.},
author = {Dankelmann, P., Swart, Henda C., van den Berg, P., Goddard, Wayne, Plummer, M. D.},
journal = {Czechoslovak Mathematical Journal},
keywords = {minimal claw-free; degree; bow-tie; line graph; minimal claw-free graph; mcf graph; degree; bow-tie; line graph; mcf line graph},
language = {eng},
number = {3},
pages = {787-798},
publisher = {Institute of Mathematics, Academy of Sciences of the Czech Republic},
title = {Minimal claw-free graphs},
url = {http://eudml.org/doc/37868},
volume = {58},
year = {2008},
}
TY - JOUR
AU - Dankelmann, P.
AU - Swart, Henda C.
AU - van den Berg, P.
AU - Goddard, Wayne
AU - Plummer, M. D.
TI - Minimal claw-free graphs
JO - Czechoslovak Mathematical Journal
PY - 2008
PB - Institute of Mathematics, Academy of Sciences of the Czech Republic
VL - 58
IS - 3
SP - 787
EP - 798
AB - 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.
LA - eng
KW - minimal claw-free; degree; bow-tie; line graph; minimal claw-free graph; mcf graph; degree; bow-tie; line graph; mcf line graph
UR - http://eudml.org/doc/37868
ER -
References
top- Chartrand, G., Lesniak, L., Graphs & Digraphs, Third edition, Chapman and Hall, London (1996). (1996) Zbl0890.05001MR1408678
- 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). (2005) Zbl1109.05092MR2187738
- Faudree, R., Flandrin, E., Ryjáček, Z., 10.1016/S0012-365X(96)00045-3, Discrete Math. 164 (1997), 87-147. (1997) MR1432221DOI10.1016/S0012-365X(96)00045-3
- Plummer, M. D., A note on Hamilton cycles in claw-free graphs, Congr. Numer. 96 (1993), 113-122. (1993) Zbl0801.05048MR1267307
- Plummer, M. D., 10.1016/0012-365X(94)90171-6, Discrete Math. 125 (1994), 301-307. (1994) Zbl0798.05041MR1263759DOI10.1016/0012-365X(94)90171-6
- Ryjáček, Z., 10.1006/jctb.1996.1732, J. Combin. Theory Ser. B 70 (1997), 217-224. (1997) MR1459867DOI10.1006/jctb.1996.1732
- Sedláček, J., Some properties of interchange graphs, 1964 Theory of Graphs and its Applications, Academic Press, Prague 145-150. MR0173255
- Sumner, D. P., 10.1017/S0017089500002652, Glasgow Math. J. 17 (1976), 12-16. (1976) Zbl0328.05132MR0409272DOI10.1017/S0017089500002652
- Rooij, A. C. M. van, Wilf, H. S., 10.1007/BF01904834, Acta Math. Acad. Sci. Hungar. 16 (1965), 263-269. (1965) MR0195761DOI10.1007/BF01904834
NotesEmbed ?
topYou must be logged in to post comments.
To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.