2021/06/14 by Kuźnar, Artur
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2106.07772
A graph G is said to be (H;k) -vertex stable if G contains a~subgraph isomorphic to H even after removing any k of its vertices alongside with their incident edges. We will denote by stab(H;k) the minimum size among sizes of all (H;k) -vertex stable graphs. In this paper we consider a~case where the structure H is a~star graph K1,r and the the number of vertices in G is exact, \ie equal to 1 + r + k . We will show that under the above assumptions stab(K1,r;k) equals either (1)/(2)(k + 1)(2r + k) , (1)/(2)((r + k)2 - 1) or (1)/(2)(r + k)2 . Moreover, we will characterize all the extremal graphs.