Article
Full entry |
PDF
(0.3 MB)
Feedback
PDF
(0.3 MB)
Feedback
Summary:
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.
References:
[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 10.1016/0012-365X(84)90061-X | MR 0740426 | Zbl 0576.05057
[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 0459.00006
[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 0778402 | Zbl 0556.05027
[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 10.1002/jgt.3190130606 | MR 1025892
[HH] C.A. Holzmann and F. Harary: On the tree graph of a matroid. SIAM J. Appl. Math. 22 (1972), 187–193. DOI 10.1137/0122021 | MR 0307952
[Lin] Y. X. Lin: A simpler proof of interpolation theorem for spanning trees. Kexue Tongbao (English edition) 30 (1985), 134. MR 0795526
[Lewinter] M. Lewinter: Interpolation theorem for the number of degree-preserving vertices of spanning trees. IEEE Trans. Circuit and Systems 34 (1987), 205. DOI 10.1109/TCS.1987.1086107 | MR 0874697
[Schuster] S. Schuster: Interpolation theorem for the number of end-vertices of spanning trees. J. Graph Theory 7 (1983), 203–208. DOI 10.1002/jgt.3190070209 | MR 0698702 | Zbl 0482.05032
[Welsh] D.J.A. Welsh: Matroid Theory. Academic Press, London, 1976. MR 0427112 | Zbl 0343.05002
[Zhou1] S.M. Zhou: Matroid tree graphs and interpolation theorems. Discrete Math. 137 (1995), 395–397. DOI 10.1016/0012-365X(95)91429-T | MR 1312476 | Zbl 0812.05065
[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 0943.05082
Search
Partner of
