Geodesic
On Minimum (Kq, k) Stable Graphs
Discussiones Mathematicae. Graph Theory, Tome 33 (2013) no. 1, pp. 101-115.

Voir la notice de l'article provenant de la source Library of Science

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 Żak in the paper On (Kq; k)-stable graphs, ( doi:/10.1002/jgt.21705) has proved a conjecture of Dudek, Szymański 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, κ(q)) stable graphs of minimum size where κ(q) is the maximum value for which for every nonnegative integer k lt; κ(q) the only (Kq, k) stable graph of minimum size is Kq+k and by determining the exact value of κ(q).
Keywords: stable graphs 
@article{DMGT_2013_33_1_a8,
     author = {Fouquet, J.L. and Thuillier, H. and Vanherpe, J.M. and Wojda, A.P.},
     title = {On {Minimum} {(K\protect\textsubscript{q},} k) {Stable} {Graphs}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {101--115},
     publisher = {mathdoc},
     volume = {33},
     number = {1},
     year = {2013},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2013_33_1_a8/}
}
TY  - JOUR
AU  - Fouquet, J.L.
AU  - Thuillier, H.
AU  - Vanherpe, J.M.
AU  - Wojda, A.P.
TI  - On Minimum (Kq, k) Stable Graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2013
SP  - 101
EP  - 115
VL  - 33
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2013_33_1_a8/
LA  - en
ID  - DMGT_2013_33_1_a8
ER  - 
%0 Journal Article
%A Fouquet, J.L.
%A Thuillier, H.
%A Vanherpe, J.M.
%A Wojda, A.P.
%T On Minimum (Kq, k) Stable Graphs
%J Discussiones Mathematicae. Graph Theory
%D 2013
%P 101-115
%V 33
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2013_33_1_a8/
%G en
%F DMGT_2013_33_1_a8
Fouquet, J.L.; Thuillier, H.; Vanherpe, J.M.; Wojda, A.P. On Minimum (Kq, k) Stable Graphs. Discussiones Mathematicae. Graph Theory, Tome 33 (2013) no. 1, pp. 101-115. http://geodesic.mathdoc.fr/item/DMGT_2013_33_1_a8/

[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

[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.

[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

[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

[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

[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