Deprecated: $wgMWOAuthSharedUserIDs=false is deprecated, set $wgMWOAuthSharedUserIDs=true, $wgMWOAuthSharedUserSource='local' instead [Called from MediaWiki\HookContainer\HookContainer::run in /var/www/html/w/includes/HookContainer/HookContainer.php at line 135] in /var/www/html/w/includes/Debug/MWDebug.php on line 372
A problem of tree graph - MaRDI portal

A problem of tree graph (Q1823250)

From MaRDI portal





scientific article; zbMATH DE number 4114653
Language Label Description Also known as
English
A problem of tree graph
scientific article; zbMATH DE number 4114653

    Statements

    A problem of tree graph (English)
    0 references
    0 references
    0 references
    1989
    0 references
    The authors prove three theorems on tree graphs. Suppose G be a graph with two edge-disjoint spanning trees. Define the tree graph \(\tau_ 2(G)\) to be the graph whose vertices are the ordered triplets \((E_ 1,E_ 2,E_ 3)\) of subsets of E(G) that partition E(G) such that \(E_ 1\) and \(E_ 2\) are edge-sets of spanning trees of G. Two vertices \((E_ 1,E_ 2,E_ 3)\) and \((F_ 1,F_ 2,F_ 3)\) in \(\tau_ 2(G)\) are adjacent iff \(\sum^{3}_{j=1}| E_ j-F_ j| =2.\) The theorems are as follows: The minimum degree \(\delta (\tau_ 2(G))\geq | V(G)| -1\) for \(\tau_ 2(G)\), and this lower bound is the best possible. The vertex set size \(| V(\tau_ 2(G))| \geq 2^{| V(G)| -1}\) for \(\tau_ 2(G)\), and this lower bound is the best possible. If \(| V(G)| \geq 3\), then \(\tau_ 2(G)\) is 2-edge-connected.
    0 references
    edge connectivity
    0 references
    tree graphs
    0 references

    Identifiers