Interpolation theorems for a family of spanning subgraphs (Q4700044)

If \(F\) is a family of graphs and \(\varphi \) is an integer-valued graph invariant such that the values \(\varphi (H)\) for \(H\in F\) form an integer interval, then we say that \(\varphi \) interpolates over \(F\). The family of spanning subgraphs of a graph \(G\) which have \(i\) edges is denoted by \(C_i(G)\). \(A\) simple edge transformation (SET) deletes one edge \(e_1\) from a graph \(H\) and adds another edge \(e_2\) to it in order to obtain a new graph \(H'\). If \(e_1\), \(e_2\) have a common end vertex, then this is an adjacent edge transformation (AET). An integer-valued invariant \(\varphi \) is said to be continuous with respect to SET (or AET), if for each SET (or AET respectively) of the form \(H\rightarrow H'\) the inequality \(| \varphi (H) - \varphi (H')| \leq 1\) holds. By \(M_j(\varphi)(H)\) is denoted the maximum and by \(m_j(\varphi)(H)\) the minimum of \(\varphi (T)\) taken over all \(T\in C_j(H)\). The main result states that both \(M_j (\varphi)\) and \(m_j(\varphi)\) interpolate over \(C_i (G)\), if either \(\varphi \) is continuous with respect to SET for \(p-\omega \leq j\leq i \leq q\), or \(\varphi \) is continuous with respect to AET for \(p-\omega = j \leq i \leq q\), where \(p,q,\omega \) denote the numbers of vertices, of edges and of connected components of \(G\).