Name
Abstract | ||
|---|---|---|
Let T be a tree. The set of leaves of T is denoted by Leaf(T). The subtree $$T-Leaf(T)$$T-Leaf(T) is called the stem of T. A spider is a tree having at most one vertex with degree greater than two. In Gargano et al. (Discrete Math 285:83---95, 2004), it is shown that if a connected graph G satisfies $$\\delta (G)\\ge (|G|-1)/3$$¿(G)¿(|G|-1)/3, then G has a spanning spider. In this paper, we prove that if $$\\sigma _4^4(G)\\ge |G|-5$$¿44(G)¿|G|-5, then G has a spanning tree whose stem is a spider, where $$\\sigma _4^4(G)$$¿44(G) denotes the minimum degree sum of four vertices of G such that the distance between any two of their vertices are at least four. Moreover, we show that this condition is sharp. |
Year | DOI | Venue |
|---|---|---|
2015 | 10.1007/s00373-015-1618-2 | Graphs and Combinatorics |
Keywords | Field | DocType |
Spanning tree, Spider, Stem | Discrete mathematics,Combinatorics,Vertex (geometry),Tree (data structure),Spanning tree,Sigma,Shortest-path tree,Connectivity,Mathematics | Journal |
Volume | Issue | ISSN |
31 | 6 | 1435-5914 |
Citations | PageRank | References |
0 | 0.34 | 2 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Mikio Kano | 1 | 548 | 99.79 |
| Zheng Yan | 2 | 0 | 2.37 |