Interpolation theorems for a family of spanning subgraphs

Zhou, Sanming

Czechoslovak Mathematical Journal, Tome 48 (1998) no. 1, pp. 45-53.

Résumé

Let $G$ be a graph with order $p$, size $q$ and component number $\omega $. For each $i$ between $p - \omega $ and $q$, let ${\mathcal C}_{i}(G)$ be the family of spanning $i$-edge subgraphs of $G$ with exactly $\omega $ components. For an integer-valued graphical invariant $\varphi $, if $H \rightarrow H^{\prime }$ is an adjacent edge transformation (AET) implies $|\varphi (H) - \varphi (H^{\prime })| \le 1$, then $\varphi $ is said to be continuous with respect to AET. Similarly define the continuity of $\varphi $ with respect to simple edge transformation (SET). Let $M_{j}(\varphi )$ and $m_{j}(\varphi )$ be the invariants defined by $M_{j}(\varphi )(H) = \max _{T \in {\mathcal C}_{j}(H)} \varphi (T)$, $ m_{j}(\varphi )(H) = \min _{T \in {\mathcal C}_{j}(H)} \varphi (T) $. It is proved that both $M_{p - \omega }(\varphi )$ and $m_{p - \omega }(\varphi )$ interpolate over $\mathbf{{\mathcal C}_{i}(G)}$, $ p - \omega \le i \le q$, if $\varphi $ is continuous with respect to AET, and that $M_{j}(\varphi )$ and $m_{j}(\varphi )$ interpolate over $\mathbf{{\mathcal C}_{i}(G)}$, $p - \omega \le j \le i \le q$, if $\varphi $ is continuous with respect to SET. In this way a lot of known interpolation results, including a theorem due to Schuster etc., are generalized.

Détail

Classification : 05C99