Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: stable graphs

Sortuj według:

Ogranicz wyniki do:

On Minimum (Kq, K) Stable Graphs

100%

Fouquet J. L., Thuillier H., Vanherpe J. M., Wojda A. P.

Discussiones Mathematicae Graph Theory

2013

tom 33

nr 1

101-115

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

Ograniczanie wyników

1 Discussiones Mathematicae Graph Theory

1 Fouquet J. L.

1 Thuillier H.

1 Vanherpe J. M.

1 Wojda A. P.

1 2013

Wyniki wyszukiwania

On Minimum (Kq, K) Stable Graphs