scientific article; zbMATH DE number 4010534

From MaRDI portal
Publication:3760558





[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.











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)