A property on edge-disjoint spanning trees (Q1922872)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | A property on edge-disjoint spanning trees |
scientific article |
Statements
A property on edge-disjoint spanning trees (English)
0 references
21 April 1997
0 references
Let \(G\) be a simple graph with \(n\) vertices and \(k(n-1)\) edges. For a partition \(\{X_1,\dots,X_k\}\) of \(E(G)\) with \(|X_i|=n-1\) for \(i=1,\dots,k\), denote \(\omega_i\) the number of components for the spanning subgraph with edge set \(X_i\). \(\varepsilon(G)\) is the minimum of \(\sum^k_{i=1} \omega_i\)---\(k\) taken over all such partitions. The paper proves that if \(\varepsilon(G)>0\) then there are always an edge \(e\) in \(G\) and an edge \(e'\) in the complement of \(G\) such that \(\varepsilon(G-e+e')<\varepsilon(G)\).
0 references
spanning trees
0 references
partition
0 references