Vulnerability bounds on the number of spanning tree leaves

Gábor Salamon


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.


spanning tree leaves, vulnerability, Hamiltonian path

Full Text:



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