Name
Abstract | ||
|---|---|---|
A spanning tree T of a graph G is called a homeomorphically irreducible spanning tree (HIST) if T does not contain vertices of degree 2. A graph G is called locally connected if, for every vertex v ∈ V(G), the subgraph induced by the neighbourhood of v is connected. In this paper, we prove that every connected and locally connected graph with more than 3 vertices contains a HIST. Consequently, we confirm the following conjecture due to Archdeacon: every graph that triangulates some surface has a HIST, which was proposed as a question by Albertson, Berman, Hutchinson and Thomassen. |
Year | DOI | Venue |
|---|---|---|
2012 | 10.1017/S0963548311000526 | Combinatorics, Probability & Computing |
Keywords | DocType | Volume |
following conjecture,graph G,Homeomorphically irreducible,homeomorphically irreducible,vertex v | Journal | 21 |
Issue | ISSN | Citations |
1-2 | 0963-5483 | 6 |
PageRank | References | Authors |
1.45 | 0 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| G. Chen | 1 | 32 | 8.36 |
| Han Ren | 2 | 23 | 7.51 |
| Songling Shan | 3 | 20 | 9.16 |