Abstract | ||
---|---|---|
Let k ≥ 2 be an integer. We show that if G is a (k + 1)-connected graph and each pair of nonadjacent vertices in G has degree sum at least |G| + 1, then for each subset S of V(G) with |S| = k, G has a spanning tree such that S is the set of endvertices. This result generalizes Ore’s theorem which guarantees the existence of a Hamilton path connecting any two vertices. |
Year | DOI | Venue |
---|---|---|
2008 | 10.1007/s00373-007-0768-2 | Graphs and Combinatorics |
Keywords | DocType | Volume |
leaf connected,hamilton path,hamilton-connected,nonadjacent vertex,spanning tree,connected graph,specified leaves,degree sum | Journal | 24 |
Issue | ISSN | Citations |
1 | 1435-5914 | 4 |
PageRank | References | Authors |
0.68 | 2 | 4 |
Name | Order | Citations | PageRank |
---|---|---|---|
Yoshimi Egawa | 1 | 4 | 0.68 |
Haruhide Matsuda | 2 | 60 | 11.74 |
Tomoki Yamashita | 3 | 96 | 22.08 |
Kiyoshi Yoshimoto | 4 | 133 | 22.65 |