### Vulnerability bounds on the number of spanning tree leaves

#### Abstract

Hamiltonicity and vulnerability of graphs are in a strong connection. A basic necessary condition states that a graph containing a 2-leaf spanning tree (that is a Hamiltonian path) cannot be split into more than

*k*+ 1 components by deleting*k*of its vertices. In this paper we consider a more general approach and investigate the connection between the number of spanning tree leaves and two vulnerability parameters namely scattering number sc(*G*) and cut-asymmetry ca(*G*). We prove that any spanning tree of a graph*G*has at least sc(*G*) + 1 leaves. We also show that if*X*$\subset$*V*is a maximum cardinality independent set of*G*= (*V*,*E*) such that the elements of*X*are all leaves of a particular spanning tree then |*X*| = ca(*G*) + 1 = |*V*| − cvc(*G*), where cvc(*G*) is the size of a minimum connected vertex cover of*G*. As a consequence we obtain a new proof for the following results: any spanning tree with independent leaves provides a 2-approximation for both MaximumInternalSpanningTree and MinimumConnectedVertexCover problems. We also consider the opposite point of view by fixing the number of leaves to*q*and looking for a*q*-leaf subtree of*G*that spans a maximum number of vertices. Bermond proved that a 2-connected graph on*n*vertices always contains a path (a 2-leaf subtree) of length min {n,δ_{2}}, where δ_{2}is the minimum degree-sum of a 2-element independent set. We generalize this result to obtain a sufficient condition for the existence of a large*q*-leaf subtree.#### Keywords

spanning tree leaves, vulnerability, Hamiltonian path

DOI: https://doi.org/10.26493/1855-3974.37.5b9

ISSN: 1855-3974

Issues from Vol 6, No 1 onward are partially supported by the Slovenian Research Agency from the Call for co-financing of scientific periodical publications