Abstract | ||
---|---|---|
A spanning tree with small diameter of a graph has many applications. In this paper we first make the following conjecture and show that the condition is best possible if it is true. If a connected graph G satisfies delta (G)>= 3|G|/(d+2), then G has a spanning tree with diameter at most d, where d >= 4 is an integer. We next prove that the conjecture holds if d >= 4 is even or d is an element of {5,7,9}. Moreover, we prove that if d >= 5 is odd and delta (G)>= 3|G|/(d+1), then G has a spanning tree with diameter at most d. |
Year | DOI | Venue |
---|---|---|
2020 | 10.1016/j.akcej.2019.03.010 | AKCE INTERNATIONAL JOURNAL OF GRAPHS AND COMBINATORICS |
Keywords | DocType | Volume |
Spanning tree, Diameter, Minimum degree | Journal | 17 |
Issue | ISSN | Citations |
1 | 0972-8600 | 0 |
PageRank | References | Authors |
0.34 | 0 | 2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Mikio Kano | 1 | 548 | 99.79 |
Hajime Matsumura | 2 | 32 | 7.29 |