On Minimum (Kq, K) Stable Graphs
J.L. Fouquet; H. Thuillier; J.M. Vanherpe; A.P. Wojda
Discussiones Mathematicae Graph Theory (2013)
- Volume: 33, Issue: 1, page 101-115
- ISSN: 2083-5892
Access Full Article
top
Abstract
topHow to cite
topJ.L. Fouquet, et al. "On Minimum (Kq, K) Stable Graphs." Discussiones Mathematicae Graph Theory 33.1 (2013): 101-115. <http://eudml.org/doc/267619>.
@article{J2013,
abstract = {A graph G is a (Kq, k) stable graph (q ≥ 3) if it contains a Kq after deleting any subset of k vertices (k ≥ 0). Andrzej ˙ Zak in the paper On (Kq; k)-stable graphs, ( doi:/10.1002/jgt.21705) has proved a conjecture of Dudek, Szyma´nski and Zwonek stating that for sufficiently large k the number of edges of a minimum (Kq, k) stable graph is (2q − 3)(k + 1) and that such a graph is isomorphic to sK2q−2 + tK2q−3 where s and t are integers such that s(q − 1) + t(q − 2) − 1 = k. We have proved (Fouquet et al. On (Kq, k) stable graphs with small k, Elektron. J. Combin. 19 (2012) #P50) that for q ≥ 5 and k ≤ q 2 +1 the graph Kq+k is the unique minimum (Kq, k) stable graph. In the present paper we are interested in the (Kq, k(q)) stable graphs of minimum size where k(q) is the maximum value for which for every nonnegative integer k},
author = {J.L. Fouquet, H. Thuillier, J.M. Vanherpe, A.P. Wojda},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {stable graphs},
language = {eng},
number = {1},
pages = {101-115},
title = {On Minimum (Kq, K) Stable Graphs},
url = {http://eudml.org/doc/267619},
volume = {33},
year = {2013},
}
TY - JOUR
AU - J.L. Fouquet
AU - H. Thuillier
AU - J.M. Vanherpe
AU - A.P. Wojda
TI - On Minimum (Kq, K) Stable Graphs
JO - Discussiones Mathematicae Graph Theory
PY - 2013
VL - 33
IS - 1
SP - 101
EP - 115
AB - A graph G is a (Kq, k) stable graph (q ≥ 3) if it contains a Kq after deleting any subset of k vertices (k ≥ 0). Andrzej ˙ Zak in the paper On (Kq; k)-stable graphs, ( doi:/10.1002/jgt.21705) has proved a conjecture of Dudek, Szyma´nski and Zwonek stating that for sufficiently large k the number of edges of a minimum (Kq, k) stable graph is (2q − 3)(k + 1) and that such a graph is isomorphic to sK2q−2 + tK2q−3 where s and t are integers such that s(q − 1) + t(q − 2) − 1 = k. We have proved (Fouquet et al. On (Kq, k) stable graphs with small k, Elektron. J. Combin. 19 (2012) #P50) that for q ≥ 5 and k ≤ q 2 +1 the graph Kq+k is the unique minimum (Kq, k) stable graph. In the present paper we are interested in the (Kq, k(q)) stable graphs of minimum size where k(q) is the maximum value for which for every nonnegative integer k
LA - eng
KW - stable graphs
UR - http://eudml.org/doc/267619
ER -
References
top- [1] J.A. Bondy and U.S.R. Murty, Graph Theory, 244 ( Springer, Series Graduate Texts in Mathematics, 2008).
- [2] A. Dudek, A. Szymański and M. Zwonek, (H, k) stable graphs with minimum size, Discuss. Math. Graph Theory 28 (2008) 137-149. doi:10.7151/dmgt.1397[Crossref]
- [3] J.-L. Fouquet, H. Thuillier, J.-M. Vanherpe and A.P. Wojda, On (Kq, k) stable graphs with small k, Electron. J. Combin. 19 (2012) #P50. Zbl1244.05123
- [4] J.-L. Fouquet, H. Thuillier, J.-M. Vanherpe and A.P. Wojda, On (Kq, k) vertex stable graphs with minimum size, Discrete Math. 312 (2012) 2109-2118. doi:10.1016/j.disc.2011.04.017[WoS][Crossref] Zbl1244.05123
- [5] P. Frankl and G.Y. Katona, Extremal k-edge-hamiltonian hypergraphs, Discrete Math. 308 (2008) 1415-1424. doi:10.1016/j.disc.2007.07.074[WoS][Crossref]
- [6] G.Y. Katona and I. Horváth, Extremal P4-stable graphs, Discrete Appl. Math. 159 (2011) 1786-1792. doi:10.1016/j.dam.2010.11.016[Crossref] Zbl1228.05187
- [7] J.J. Sylvester, Question 7382, Mathematical Questions from the Educational Times, (1884) 41:21.
- [8] A. Żak, On (Kq; k)-stable graphs, J. Graph Theory, (2012),to appear. doi:/10.1002/jgt.21705
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.