Interpolation theorems for a family of spanning subgraphs

Zhou, San Ming. "Interpolation theorems for a family of spanning subgraphs." Czechoslovak Mathematical Journal 48.1 (1998): 45-53. <http://eudml.org/doc/30400>.

@article{Zhou1998,
abstract = {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.},
author = {Zhou, San Ming},
journal = {Czechoslovak Mathematical Journal},
keywords = {interpolation of graph invariants; invariant continuous with respect to a transformation},
language = {eng},
number = {1},
pages = {45-53},
publisher = {Institute of Mathematics, Academy of Sciences of the Czech Republic},
title = {Interpolation theorems for a family of spanning subgraphs},
url = {http://eudml.org/doc/30400},
volume = {48},
year = {1998},
}

TY - JOUR
AU - Zhou, San Ming
TI - Interpolation theorems for a family of spanning subgraphs
JO - Czechoslovak Mathematical Journal
PY - 1998
PB - Institute of Mathematics, Academy of Sciences of the Czech Republic
VL - 48
IS - 1
SP - 45
EP - 53
AB - 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.
LA - eng
KW - interpolation of graph invariants; invariant continuous with respect to a transformation
UR - http://eudml.org/doc/30400
ER -