(H,k) stable graphs with minimum size

Aneta Dudek; Artur Szymański; Małgorzata Zwonek

ArticleOriginal scientific text

Title

(H,k) stable graphs with minimum size

Authors ¹, ¹, ¹

Affiliations

Faculty of Applied Mathematics AGH, Mickiewicza 30, 30-059 Kraków, Poland

Abstract

Let us call a G (H,k) graph vertex stable if it contains a subgraph H ever after removing any of its k vertices. By Q(H,k) we will denote the minimum size of an (H,k) vertex stable graph. In this paper, we are interested in finding Q(₃,k), Q(₄,k),

Q (K_{1, p}, k)

and Q(Kₛ,k).

Keywords

ENG

graph, stable graph

P. Frankl and G.Y. Katona, Extremal k-edge-hamiltonian hypergraphs, accepted for publication in Discrete Math.
I. Horváth and G.Y. Katona, Extremal stable graphs, manuscript.
R. Greenlaw and R. Petreschi, Cubic Graphs, ACM Computing Surveys, No. 4, (1995).

Title

(H,k) stable graphs with minimum size

Affiliations

Abstract

Keywords

Bibliography