×

Interpolation theorems for the independence and domination numbers of spanning trees. (English) Zbl 0681.05020

Graph theory in memory of G. A. Dirac, Pap. Meet., Sandbjerg/Den. 1985, Ann. Discrete Math. 41, 221-227 (1989).
[For the entire collection see Zbl 0656.00008.]
Denote the node independence number of a graph G by \(\beta_ 0\), the edge independence number by \(\beta_ 1\), the domination number by \(\alpha_{00}\) and the independent domination number by \(\alpha '_{00}\). Let m, n, k be three integers, \(m<k<n\) and let T, \(T^*\) be any two spanning trees of a given connected graph G. Then the next three interpolation theorems hold.
(1) If \(\beta_ 0(T)=m\), \(\beta_ 0(T^*)=n\), then there exists a spanning tree \(T'\) such that \(\beta_ 0(T')=k.\)
(2) If \(\beta_ 1(T)=m\), \(\beta_ 1(T^*)=n\), then there exists a spanning tree \(T'\) such that \(\beta_ 1(T')=k.\)
(3) If \(\alpha_{00}(T)=m\), \(\alpha_{00}(T^*)=n\), then there exists a spanning tree \(T'\) such that \(\alpha_{00}(T')=k.\)
On the contrary an analogical theorem is not true for the independent domination number \(\alpha '_{00}.\)
Two other interpolation theorems concerning the diameter and the number of endpoints were presented by the same authors separately in 1983.
Reviewer: M.Koman

MSC:

05C05 Trees
05C99 Graph theory

Citations:

Zbl 0656.00008