Interpolation theorems on graph parameters
Suppose \(\mathcal{C}\) \ is a class of graphs and \(f\) maps \(\mathcal{C}\) into the integers. Then \(f\) ``interpolates'' on \(\mathcal{C}\) if it is true that whenever \(G_{1},G_{2}\in \mathcal{C}\) and \( f(G_{1})<n<f(G_{2})\), there is an \(H\in \mathcal{C}\) with \(f(H)=n\). For instance, if \(\mathcal{C}\) consists of the spanning trees of a given 2-connected graph \(G\) then \textit{E. Harary, R. J. Mokken} and \textit{M.J. Plantholt} [IEEE Trans. Circuits Syst. 30, 429--432 (1983; Zbl 0528.05019)] showed that the diameter interpolates on \(\mathcal{C}\). In the paper under review the author observes that if \(\mathcal{C}\) contains all the graphs with a given degree sequence then the independence number, the matching number, the vertex covering number, the edge covering number and the domination number all interpolate on \(\mathcal{C}\).
scientific article; zbMATH DE number 2144213