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.7529817223548889
0 references
0.7462142705917358
0 references
0.737971305847168
0 references
0.7289160490036011
0 references
0.7281686067581177
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