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 $\phi$, if $H\to H^{\prime }$ is an adjacent edge transformation (AET) implies $|\phi (H)-\phi (H^{\prime })|\le 1$, then $\phi$ is said to be continuous with respect to AET. Similarly define the continuity of $\phi$ with respect to simple edge transformation (SET). Let $M_j(\phi )$ and $m_j(\phi )$ be the invariants defined by $M_j(\phi )(H)=\underset{T\in {\mathcal{C}}_j(H)}{max}\phi (T)$, $m_j(\phi )(H)=\underset{T\in {\mathcal{C}}_j(H)}{min}\phi (T)$. It is proved that both $M_{p-\omega }(\phi )$ and $m_{p-\omega }(\phi )$ interpolate over ${\mathcal{C}}_{\mathbf{i}}\mathbf{(}\mathbf{G})$, $p-\omega \le i\le q$, if $\phi$ is continuous with respect to AET, and that $M_j(\phi )$ and $m_j(\phi )$ interpolate over ${\mathcal{C}}_{\mathbf{i}}\mathbf{(}\mathbf{G})$, $p-\omega \le j\le i\le q$, if $\phi$ 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