On Minimum (Kq, K) Stable Graphs
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...
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
University of Zielona Góra
2013-03-01
|
| Series: | Discussiones Mathematicae Graph Theory |
| Subjects: | |
| Online Access: | https://doi.org/10.7151/dmgt.1656 |
| _version_ | 1797704420809506816 |
|---|---|
| author | Fouquet J.L. Thuillier H. Vanherpe J.M. Wojda A.P. |
| author_facet | Fouquet J.L. Thuillier H. Vanherpe J.M. Wojda A.P. |
| author_sort | Fouquet J.L. |
| collection | DOAJ |
| description | 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 <k(q) the only (Kq, k) stable graph of minimum size is Kq+k and by determining the exact value of k(q). |
| first_indexed | 2024-03-12T05:20:10Z |
| format | Article |
| id | doaj.art-cea2425c9634416587d0e745cdddb45a |
| institution | Directory Open Access Journal |
| issn | 2083-5892 |
| language | English |
| last_indexed | 2024-03-12T05:20:10Z |
| publishDate | 2013-03-01 |
| publisher | University of Zielona Góra |
| record_format | Article |
| series | Discussiones Mathematicae Graph Theory |
| spelling | doaj.art-cea2425c9634416587d0e745cdddb45a2023-09-03T07:47:22ZengUniversity of Zielona GóraDiscussiones Mathematicae Graph Theory2083-58922013-03-0133110111510.7151/dmgt.1656On Minimum (Kq, K) Stable GraphsFouquet J.L.0Thuillier H.1Vanherpe J.M.2Wojda A.P.3L.I.F.O., Faculté des Sciences, B.P. 6759 Université d’Orléans, 45067 Orléans Cedex 2, FranceL.I.F.O., Faculté des Sciences, B.P. 6759 Université d’Orléans, 45067 Orléans Cedex 2, FranceL.I.F.O., Faculté des Sciences, B.P. 6759 Université d’Orléans, 45067 Orléans Cedex 2, FranceWydzia l Matematyki Stosowanej Zak lad Matematyki Dyskretnej A.G.H., Al. Mickiewicza 30, 30-059 Kraków, PolandA 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 <k(q) the only (Kq, k) stable graph of minimum size is Kq+k and by determining the exact value of k(q).https://doi.org/10.7151/dmgt.1656stable graphs |
| spellingShingle | Fouquet J.L. Thuillier H. Vanherpe J.M. Wojda A.P. On Minimum (Kq, K) Stable Graphs Discussiones Mathematicae Graph Theory stable graphs |
| title | On Minimum (Kq, K) Stable Graphs |
| title_full | On Minimum (Kq, K) Stable Graphs |
| title_fullStr | On Minimum (Kq, K) Stable Graphs |
| title_full_unstemmed | On Minimum (Kq, K) Stable Graphs |
| title_short | On Minimum (Kq, K) Stable Graphs |
| title_sort | on minimum kq k stable graphs |
| topic | stable graphs |
| url | https://doi.org/10.7151/dmgt.1656 |
| work_keys_str_mv | AT fouquetjl onminimumkqkstablegraphs AT thuillierh onminimumkqkstablegraphs AT vanherpejm onminimumkqkstablegraphs AT wojdaap onminimumkqkstablegraphs |