Characterization of graphs of diameter 2 containing a homeomorphically irreducible spanning tree

A spanning tree of a graph with no vertex of degree 2 is called a homeomorphically irreducible spanning tree (HIST) of the graph. In 1990, Albertson, Berman, Hutchinson, and Thomassen conjectured that every twin‐free graph with diameter 2 contains a HIST. Recently, Ando disproved this conjecture and...

Full description

Saved in:
Bibliographic Details
Published in:Journal of graph theory 2023-12, Vol.104 (4), p.886-903
Main Authors: Shan, Songling, Tsuchiya, Shoichi
Format: Article
Language:English
Subjects:
diameter 2 graph
Graph theory
Graphs
homeomorphically irreducible spanning tree
spanning tree
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:A spanning tree of a graph with no vertex of degree 2 is called a homeomorphically irreducible spanning tree (HIST) of the graph. In 1990, Albertson, Berman, Hutchinson, and Thomassen conjectured that every twin‐free graph with diameter 2 contains a HIST. Recently, Ando disproved this conjecture and characterized twin‐free graphs with diameter 2 that do contain a HIST. In this paper, we give a complete characterization of all graphs of diameter 2 that contain a HIST. This characterization gives alternative proofs for several known results.
ISSN:0364-9024
1097-0118
DOI:10.1002/jgt.23005