0 KB364 KB39 KB200820252009Salamon, Gáborštevilka:1letnik:2str. 77-92COBISSID:15159897ISSN:1855-3966URN:URN:NBN:SI:doc-RO9JQN7LenDruštvo matematikov, fizikov in astronomov SlovenijeArs mathematica contemporaneamatematikateorija grafovVulnerability bounds on the number of spanning tree leaves|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| = {\rm ca}(G) + 1 = |V| - {\rm 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 Maximum Internal Spanning Tree and Minimum Connected Vertex Cover 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,\delta_2\}$?, where ?$\delta_2$? is the minimum degree-sum ofa 2-element independent set. We generalize this result to obtain a sufficient condition for the existence of a large ?$q$?-leaf subtreeTEXTznanstveno časopisjejournalsSlovenian National E-content AggregatorNational and University Library of SloveniaUniverza na Primorskem, Fakulteta za naravoslovje, matematiko in informacijske tehnologije