| Title:
|
Interpolation theorems for a family of spanning subgraphs (English) |
| Author:
|
Zhou, Sanming |
| Language:
|
English |
| Journal:
|
Czechoslovak Mathematical Journal |
| ISSN:
|
0011-4642 (print) |
| ISSN:
|
1572-9141 (online) |
| Volume:
|
48 |
| Issue:
|
1 |
| Year:
|
1998 |
| Pages:
|
45-53 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| 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. (English) |
| MSC:
|
05C99 |
| idZBL:
|
Zbl 0927.05076 |
| idMR:
|
MR1614068 |
| . |
| Date available:
|
2009-09-24T10:10:52Z |
| Last updated:
|
2020-07-03 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/127397 |
| . |
| Reference:
|
[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. Zbl 0576.05057, MR 0740426, 10.1016/0012-365X(84)90061-X |
| Reference:
|
[Cai] M.C. Cai: A solution of Chartrand’s problem on spanning trees.Acta Mathematica Applicata Sinica 1 (1994), no. 2, 97–98. |
| Reference:
|
[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 |
| Reference:
|
[Harary] F. Harary: Conditional colorability in graphs.Graphs and Applications, F. Harary and J. S. Maybee (eds.), Wiley, New York, 1985, pp. 127–136. Zbl 0556.05027, MR 0778402 |
| Reference:
|
[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. MR 1025892, 10.1002/jgt.3190130606 |
| Reference:
|
[HH] C.A. Holzmann and F. Harary: On the tree graph of a matroid.SIAM J. Appl. Math. 22 (1972), 187–193. MR 0307952, 10.1137/0122021 |
| Reference:
|
[Lin] Y. X. Lin: A simpler proof of interpolation theorem for spanning trees.Kexue Tongbao (English edition) 30 (1985), 134. MR 0795526 |
| Reference:
|
[Lewinter] M. Lewinter: Interpolation theorem for the number of degree-preserving vertices of spanning trees.IEEE Trans. Circuit and Systems 34 (1987), 205. MR 0874697, 10.1109/TCS.1987.1086107 |
| Reference:
|
[Schuster] S. Schuster: Interpolation theorem for the number of end-vertices of spanning trees.J. Graph Theory 7 (1983), 203–208. Zbl 0482.05032, MR 0698702, 10.1002/jgt.3190070209 |
| Reference:
|
[Welsh] D.J.A. Welsh: Matroid Theory.Academic Press, London, 1976. Zbl 0343.05002, MR 0427112 |
| Reference:
|
[Zhou1] S.M. Zhou: Matroid tree graphs and interpolation theorems.Discrete Math. 137 (1995), 395–397. Zbl 0812.05065, MR 1312476, 10.1016/0012-365X(95)91429-T |
| Reference:
|
[Zhou4] S.M. Zhou: An interpolation theorem of graphs.A Friendly Collection of Math. Papers I, Jilin University Press, 1990, pp. 154–156. |
| Reference:
|
[Zhou2] S.M. Zhou: Several interolation theorems for graphs.Graph Theory Notes of New York XXIX (1995), 18–20. |
| Reference:
|
[Zhou3] S.M. Zhou: Conditional invariants and interpolation theorems for graphs.Submitted. Zbl 0943.05082 |
| . |
