Hostname: page-component-74656f9884-rdgjk Total loading time: 0 Render date: 2026-11-09T03:27:23.054Z Has data issue: false hasContentIssue false
  • English
  • Français

Homeomorphically Irreducible Spanning Trees in Locally Connected Graphs

Published online by Cambridge University Press:  02 February 2012

GUANTAO CHEN ,
HAN REN  and
SONGLING SHAN
GUANTAO CHEN
Affiliation:
Department of Mathematics and Statistics, Georgia State University, Atlanta, Georgia 30303, USA (e-mail: gchen@gsu.edu)
HAN REN
Affiliation:
Department of Mathematics, East China Normal University, Shanghai 200241, China
SONGLING SHAN
Affiliation:
Department of Mathematics and Statistics, Georgia State University, Atlanta, Georgia 30303, USA (e-mail: gchen@gsu.edu)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

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.

Information

Type
Paper
Information
Combinatorics, Probability and Computing , Volume 21 , Issue 1-2: Honouring the Memory of Richard H. Schelp , March 2012 , pp. 107 - 111
Copyright
Copyright © Cambridge University Press 2012

References

[1]Albertson, M. O., Berman, D. M., Hutchinson, J. P. and Thomassen, C. (1990) Graphs with homeomorphically irreducible spanning trees. J. Graph Theory 14 247–258.CrossRefGoogle Scholar
[2]Bondy, J. A. and Murty, U. S. R. (2008) Graph Theory, Vol. 244 of Graduate Texts in Mathematics, Springer.Google Scholar
[3]Beineke, L. W. and Wilson, R. J., eds (2009) Topics in Topological Graph Theory, Vol. 128 of Encyclopedia of Mathematics and its Applications, Cambridge University Press.Google Scholar
[4]Davidow, A. L., Hutchinson, J. P. and Huneke, J. P. (1995) Planar and toroidal graphs with homeomorphically irreducible spanning trees. In Graph Theory, Combinatorics, and Algorithms: Kalamazoo 1992, Vols 1 & 2, Wiley–Interscience, pp. 265–276.Google Scholar
[5]Hill, A. (1974) Graphs with homeomorphically irreducible spanning trees. In Combinatorics: Proc. British Combinatorial Conference, Aberystwyth 1973, Vol. 13 of London Mathematical Society Lecture Notes, Cambridge University Press, pp. 61–68.CrossRefGoogle Scholar
[6]Hwang, F. K., Richards, D. S. and Winter, P. (1992) The Steiner Tree Problem, Vol. 53 of Annals of Discrete Mathematics, North-Holland.Google Scholar
[7]Malkevitch, J. (1979) Spanning trees in polytopal graphs. In Second International Conference on Combinatorial Mathematics, New York 1978, Vol. 319 of Ann. New York Acad. Sci., New York Academy of Sciences, pp. 362–367.Google Scholar
[8]Ringel, G. (1978) Nonexistence of graph embeddings. In Theory and Applications of Graphs: Proc. International Conference, Kalamazoo 1976, Vol. 642 of Lecture Notes in Mathematics, Springer, pp. 465–476.CrossRefGoogle Scholar