Geodesic
Interpolation theorems for a family of spanning subgraphs
Czechoslovak Mathematical Journal, Tome 48 (1998) no. 1, pp. 45-53 Cet article a éte moissonné depuis la source Czech Digital Mathematics Library

Voir la notice de l'article

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.
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.
Classification : 05C99 
@article{CMJ_1998_48_1_a3,
     author = {Zhou, Sanming},
     title = {Interpolation theorems for a family of spanning subgraphs},
     journal = {Czechoslovak Mathematical Journal},
     pages = {45--53},
     year = {1998},
     volume = {48},
     number = {1},
     mrnumber = {1614068},
     zbl = {0927.05076},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/CMJ_1998_48_1_a3/}
}
TY  - JOUR
AU  - Zhou, Sanming
TI  - Interpolation theorems for a family of spanning subgraphs
JO  - Czechoslovak Mathematical Journal
PY  - 1998
SP  - 45
EP  - 53
VL  - 48
IS  - 1
UR  - http://geodesic.mathdoc.fr/item/CMJ_1998_48_1_a3/
LA  - en
ID  - CMJ_1998_48_1_a3
ER  - 
%0 Journal Article
%A Zhou, Sanming
%T Interpolation theorems for a family of spanning subgraphs
%J Czechoslovak Mathematical Journal
%D 1998
%P 45-53
%V 48
%N 1
%U http://geodesic.mathdoc.fr/item/CMJ_1998_48_1_a3/
%G en
%F CMJ_1998_48_1_a3
Zhou, Sanming. Interpolation theorems for a family of spanning subgraphs. Czechoslovak Mathematical Journal, Tome 48 (1998) no. 1, pp. 45-53. http://geodesic.mathdoc.fr/item/CMJ_1998_48_1_a3/

[Barefoot] C.A. Barefoot: Interpolation theorem for the number of pendant vertices of connected spanning subgraphs of equal size. Discrete Math. 49 (1984), 109–112. | DOI | MR | Zbl

[Cai] M.C. Cai: A solution of Chartrand’s problem on spanning trees. Acta Mathematica Applicata Sinica 1 (1994), no. 2, 97–98.

[Chartrand] The Theory and Applications of Graphs. Proc. Fourth Intern. Conf. on Graph Theory Applications, 1980, G. Chartrand, etc. (eds.), Wiley, New York, 1981, pp. 610. | Zbl

[Harary] F. Harary: Conditional colorability in graphs. Graphs and Applications, F. Harary and J. S. Maybee (eds.), Wiley, New York, 1985, pp. 127–136. | MR | Zbl

[HP] F. Harary and M. Plantholt: Classification of interpolation theorems for spanning trees and other families of spanning subgraphs. J. Graph Theory 13 (1989), 703–712. | DOI | MR

[HH] C.A. Holzmann and F. Harary: On the tree graph of a matroid. SIAM J. Appl. Math. 22 (1972), 187–193. | DOI | MR

[Lin] Y. X. Lin: A simpler proof of interpolation theorem for spanning trees. Kexue Tongbao (English edition) 30 (1985), 134. | MR

[Lewinter] M. Lewinter: Interpolation theorem for the number of degree-preserving vertices of spanning trees. IEEE Trans. Circuit and Systems 34 (1987), 205. | DOI | MR

[Schuster] S. Schuster: Interpolation theorem for the number of end-vertices of spanning trees. J. Graph Theory 7 (1983), 203–208. | DOI | MR | Zbl

[Welsh] D.J.A. Welsh: Matroid Theory. Academic Press, London, 1976. | MR | Zbl

[Zhou1] S.M. Zhou: Matroid tree graphs and interpolation theorems. Discrete Math. 137 (1995), 395–397. | DOI | MR | Zbl

[Zhou4] S.M. Zhou: An interpolation theorem of graphs. A Friendly Collection of Math. Papers  I, Jilin University Press, 1990, pp. 154–156.

[Zhou2] S.M. Zhou: Several interolation theorems for graphs. Graph Theory Notes of New York XXIX (1995), 18–20.

[Zhou3] S.M. Zhou: Conditional invariants and interpolation theorems for graphs. Submitted. | Zbl