| Title:
|
Interpolation theorem for a continuous function on orientations of a simple graph (English) |
| Author:
|
Zhang, Fuji |
| Author:
|
Chen, Zhibo |
| Language:
|
English |
| Journal:
|
Czechoslovak Mathematical Journal |
| ISSN:
|
0011-4642 (print) |
| ISSN:
|
1572-9141 (online) |
| Volume:
|
48 |
| Issue:
|
3 |
| Year:
|
1998 |
| Pages:
|
433-438 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| Summary:
|
Let $G$ be a simple graph. A function $f$ from the set of orientations of $G$ to the set of non-negative integers is called a continuous function on orientations of $G$ if, for any two orientations $O_1$ and $O_2$ of $G$, $|f(O_1)-f(O_2)|\le 1$ whenever $O_1$ and $O_2$ differ in the orientation of exactly one edge of $G$. We show that any continuous function on orientations of a simple graph $G$ has the interpolation property as follows: If there are two orientations $O_1$ and $O_2$ of $G$ with $f(O_1)=p$ and $f(O_2)=q$, where $p<q$, then for any integer $k$ such that $p<k<q$, there are at least $m$ orientations $O$ of $G$ satisfying $f(O) = k$, where $m$ equals the number of edges of $G$. It follows that some useful invariants of digraphs including the connectivity, the arc-connectivity and the absorption number, etc., have the above interpolation property on the set of all orientations of $G$. (English) |
| MSC:
|
05C20 |
| MSC:
|
05C40 |
| idZBL:
|
Zbl 0949.05034 |
| idMR:
|
MR1637930 |
| . |
| Date available:
|
2009-09-24T10:15:05Z |
| Last updated:
|
2020-07-03 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/127430 |
| . |
| Reference:
|
[1] 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:
|
[2] M. Cai: A solution of Chartrand’s problem on spanning trees.Acta Math. Applicatae Sinica 1 (1984), 97–98. Zbl 0574.05014, 10.1007/BF01669670 |
| Reference:
|
[3] G. Chartrand et. al., eds.: Theory and Applications of Graphs.Wiley, New York, 1980. MR 0634511 |
| Reference:
|
[4] G. Chartrand and L. Lesniak: Graphs & Digraphs, 2nd. ed..Wadsworth & Brookds, Monterey, California, 1986. MR 0834583 |
| Reference:
|
[5] V. Chvátal and G. Thomassen: Distances in orientations of graphs.J. Combin. Theory, Ser. B 24 (1978), 61–75. MR 0491326, 10.1016/0095-8956(78)90078-3 |
| Reference:
|
[6] J. Donald and J. Elwin: On the structure of the strong orientations of a graph.SIAM J. Discrete Math. 6 (1993), 30–43. MR 1201988, 10.1137/0406003 |
| Reference:
|
[7] A. M. H. Gerards: An orientation theorem for graphs.J. Combin. Theory, Ser. B 62 (1994), 199-212. Zbl 0807.05020, MR 1305048, 10.1006/jctb.1994.1064 |
| Reference:
|
[8] F. Harary, R. J. Mokken and M. Plantholt: Interpolation theorem for diameters of spanning trees.IEEE Trans. Circuits Syst. CAS-30 (1983), 429–431. MR 0715502, 10.1109/TCS.1983.1085385 |
| Reference:
|
[9] 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:
|
[10] F. Harary and S. Schuster: Interpolation theorems for the independence and domination numbers of spanning trees.Graph Theory in Memory of G. A. Dirac, to appear. MR 0976003 |
| Reference:
|
[11] F. Harary and S. Schuster: Interpolation theorems for invariants of spanning trees of a given graph: Covering numbers.The 250-th Anniversary Conference on Graph Theory, Congressus Numerantium, Utilitas Mathematica. |
| Reference:
|
[12] M. Lewinter: Interpolation theorem for the number of degree-preserving vertices of spanning trees.IEEE Trans. Circuits Syst. CAS-34 (1987), 205. MR 0874697, 10.1109/TCS.1987.1086107 |
| Reference:
|
[13] Y. Lin: A simpler proof of interpolation theorem for spanning trees.Kexue Tongbao 30 (1985), 134. MR 0795526 |
| Reference:
|
[14] G. Liu: A lower bound on solutions of Chartrand’s problem.Applicatae Sinica 1 (1984), 93–96. Zbl 0577.05024, 10.1007/BF01883897 |
| Reference:
|
[15] L. Lovácz: Topological and Algebraic Methods in Graph Theory.Graph Theory and Related Topics, A. J. Bondy and U. S. R. Murty, eds., Academic Press, New York, 1979, pp. 1–14. MR 0538032 |
| Reference:
|
[16] H. E. Robbins: A theorem on graphs, with an application to a problem of traffic control.Amer. Math. Monthly 46 (1939), 281–283. Zbl 0021.35703, MR 1524589, 10.2307/2303897 |
| Reference:
|
[17] F. S. Roberts and Y. Xu: On the optimal strongly connected operations of city street graphs I: Large grids.SIAM J. Discrete Math. 1 (1988), 199–222. MR 0941351 |
| Reference:
|
[18] F. S. Roberts and Y. Xu: On the optimal strongly connected operations of city street graphs II: Two east-west avenues or north-south streets.Networks 19 (1989), 221–233. MR 0984567, 10.1002/net.3230190204 |
| Reference:
|
[19] F. S. Roberts and Y. Xu: On the optimal strongly connected operations of city street graphs III: Three east-west avenues or north-south streets.Networks 22 (1992), 109–143. MR 1148018, 10.1002/net.3230220202 |
| Reference:
|
[20] F. S. Roberts and Y. Xu: On the optimal strongly connected operations of city street graphs IV: Four east-west avenues or north-south streets.Discrete Appl. Math. 49 (1994), 331–356. MR 1272496, 10.1016/0166-218X(94)90217-8 |
| Reference:
|
[21] 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:
|
[22] R. P. Stanley: Acyclic orientations of graphs.Discrete Math. 5 (1973), 171–178. Zbl 0258.05113, MR 0317988, 10.1016/0012-365X(73)90108-8 |
| Reference:
|
[23] F. Zhang and Z. Chen: Connectivity of (adjacency) tree graphs.J. Xinjiang Univ. 4 (1986), 1–5. MR 0919491 |
| Reference:
|
[24] F. Zhang and X. Guo: Interpolation theorem for the number of end-vertices of directed spanning trees and the connectivity of generalized directed graphs.J. Xinjiang Univ. 4 (1985), 5–7. MR 0918861 |
| Reference:
|
[25] S. 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 |
| . |
