No label defined (Q3760558)

From MaRDI portal

!

This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:

scientific article; zbMATH DE number 4010534
Language Label Description Also known as
default for all languages
No label defined
    English
    No label defined
    scientific article; zbMATH DE number 4010534

      Statements

      1986
      0 references
      spanning tree
      0 references
      radius
      0 references
      diameter
      0 references
      Cartesian product
      0 references
      0 references
      [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.
      0 references

      Identifiers