PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
2013 | 33 | 1 | 101-115
Tytuł artykułu

On Minimum (Kq, K) Stable Graphs

Treść / Zawartość
Warianty tytułu
Języki publikacji
EN
Abstrakty
EN
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
Słowa kluczowe
Wydawca
Rocznik
Tom
33
Numer
1
Strony
101-115
Opis fizyczny
Daty
wydano
2013-03-01
online
2013-04-13
Twórcy
autor
  • L.I.F.O., Faculté des Sciences, B.P. 6759 Université d’Orléans, 45067 Orléans Cedex 2, France, fouquet@univ-lemans.fr
autor
  • L.I.F.O., Faculté des Sciences, B.P. 6759 Université d’Orléans, 45067 Orléans Cedex 2, France, jmvanh@univ-lemans.fr
autor
  • Wydzia l Matematyki Stosowanej Zak lad Matematyki Dyskretnej A.G.H., Al. Mickiewicza 30, 30-059 Kraków, Poland, wojda@agh.edu.pl
Bibliografia
  • [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.
  • [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]
  • [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]
  • [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
Typ dokumentu
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.doi-10_7151_dmgt_1656
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.