Interpolation theorems on graph parameters

MaRDI QIDQ1768047zbMATH OpenFDO

Authors N. Punnim

Publication date 11 March 2005

Published in Southeast Asian Bulletin of Mathematics (Search for Journal in Brave)

zbMATH Keywords

degree sequence graph parameter interpolation

Mathematics Subject Classification ID

Vertex degrees (05C07)

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}\).

Recommendations

Cited in

(19)

This page was built for publication: Interpolation theorems on graph parameters

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1768047)