scientific article; zbMATH DE number 4010534
[For the entire collection see Zbl 0608.00004.] A spanning tree of a graph U is said to be radius (diameter) preserving if it has the same radius (diameter) as U. While every graph has a radius preserving spanning tree, it is not always the case that it contains a spanning tree which is also diameter preserving (consider \(C_ n\), for example). From spanning trees \(T_ U\) and \(T_ V\) of U and V, respectively, a type I spanning tree of \(U\times V\), the Cartesian product of U and V, is constructed by taking all copies \(T_ U\times p\) of \(T_ U\) in \(U\times V\), where p is a vertex of V, and one copy \(q\times T_ V\), where q is a central vertex of \(T_ U\). A type II spanning tree is defined similarly. It is proved that if both \(T_ U\) and \(T_ V\) are radius preserving then type I and type II spanning trees are radius preserving spanning trees of \(U\times V\). If \(T_ U\) and \(T_ V\) are diameter preserving, a condition is derived for \(U\times V\) to contain a type I or type II diameter preserving spanning tree.
- On optimal orientations of Cartesian products of trees
- A note on graphs with diameter-preserving spanning trees
- Diameter-preserving spanning trees in sparse weighted graphs
- Sharp upper and lower bounds on the number of spanning trees in Cartesian product of graphs
- An infinite class of reach-preservable graphs
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3760558)