Harary, F.; Schuster, S. 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 Cited in 3 Documents MSC: 05C05 Trees 05C99 Graph theory Keywords:independence number; domination number; spanning trees; connected graph Citations:Zbl 0656.00008 PDFBibTeX XML