A problem of tree graph (Q1823250)
From MaRDI portal
| This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: A problem of tree graph |
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
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