PDF
Discussiones Mathematicae Graph Theory 28(1) (2008)
137-149
DOI: https://doi.org/10.7151/dmgt.1397
(H,k) STABLE GRAPHS WITH MINIMUM SIZE
Aneta Dudek, Artur Szymański and Małgorzata Zwonek
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(C3,k), Q(C4,k), Q(K1,p,k) and Q(Ks,k).Keywords: graph, stable graph.
2000 Mathematics Subject Classification: 05C35.
References
| [1] | P. Frankl and G.Y. Katona, Extremal k-edge-hamiltonian hypergraphs, accepted for publication in Discrete Math. |
| [2] | I. Horváth and G.Y. Katona, Extremal stable graphs, manuscript. |
| [3] | R. Greenlaw and R. Petreschi, Cubic Graphs, ACM Computing Surveys, No. 4, (1995). |
Received 8 January 2007
Revised 16 October 2007
Accepted 26 October 2007
Close