Interpolation theorems on graph parameters
type: Item
instance of: scholarly article
title: Interpolation theorems on graph parameters
zbMATH Open document ID: 1059.05036
published in: Southeast Asian Bulletin of Mathematics
publication date: 2005-03-11T00:00:00Z
review text: 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}\).
reviewed by: L. Traldi
Mathematics Subject Classification ID: 05C07
zbMATH DE Number: 2144213
zbMATH Keywords: degree sequence
zbMATH Keywords: graph parameter
zbMATH Keywords: interpolation
author: N. Punnim
MaRDI profile type: Publication
description: scientific article; zbMATH DE number 2144213