Premium
A note on graphs with diameter‐preserving spanning trees
Author(s) -
Buckley Fred,
Lewinter Martin
Publication year - 1988
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.3190120408
Subject(s) - combinatorics , mathematics , spanning tree , shortest path tree , minimum degree spanning tree , trémaux tree , graph , path (computing) , minimum spanning tree , discrete mathematics , pathwidth , line graph , computer science , programming language
The distance between a pair of vertices u, v in a graph G is the length of a shortest path joining u and v . The diameter diam(G) of G is the maximum distance between all pairs of vertices in G . A spanning tree T of G is diameter preserving if diam( T ) = diam( G ). In this note, we characterize graphs that have diameter‐preserving spanning trees.
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom