Name
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) [10] and cut-asymmetry ca(G) [16]. We prove that any spanning tree of a graph G has at least sc(G) + 1 leaves. We also show that if X C 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 vertical bar X vertical bar = ca(G) + 1 = vertical bar V vertical bar - 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 the MAXIMUM INTERNAL SPANNING TREE [16] and the MINIMUM CONNECTED VERTEX COVER [17] 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 [2] 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 of a 2-element independent set. We generalize this result to obtain a sufficient condition for the existence of a large q-leaf subtree. |
Year | DOI | Venue |
|---|---|---|
2009 | 10.26493/1855-3974.37.5b9 | ARS MATHEMATICA CONTEMPORANEA |
Keywords | Field | DocType |
Spanning tree leaves,vulnerability,Hamiltonian path | Discrete mathematics,Topology,Combinatorics,Trémaux tree,Minimum degree spanning tree,k-minimum spanning tree,Euclidean minimum spanning tree,Connected dominating set,Spanning tree,Shortest-path tree,Mathematics,Minimum spanning tree | Journal |
Volume | Issue | ISSN |
2 | 1 | 1855-3966 |
Citations | PageRank | References |
1 | 0.36 | 6 |
Authors | ||
1 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Gábor Salamon | 1 | 46 | 3.61 |