Article
Full entry |
PDF
(0.2 MB)
Feedback
PDF
(0.2 MB)
Feedback
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$.
References:
[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. DOI 10.1016/0012-365X(84)90061-X | MR 0740426 | Zbl 0576.05057
[2] M. Cai: A solution of Chartrand’s problem on spanning trees. Acta Math. Applicatae Sinica 1 (1984), 97–98. DOI 10.1007/BF01669670 | Zbl 0574.05014
[3] G. Chartrand et. al., eds.: Theory and Applications of Graphs. Wiley, New York, 1980. MR 0634511
[4] G. Chartrand and L. Lesniak: Graphs & Digraphs, 2nd. ed. Wadsworth & Brookds, Monterey, California, 1986. MR 0834583
[5] V. Chvátal and G. Thomassen: Distances in orientations of graphs. J. Combin. Theory, Ser. B 24 (1978), 61–75. DOI 10.1016/0095-8956(78)90078-3 | MR 0491326
[6] J. Donald and J. Elwin: On the structure of the strong orientations of a graph. SIAM J. Discrete Math. 6 (1993), 30–43. DOI 10.1137/0406003 | MR 1201988
[7] A. M. H. Gerards: An orientation theorem for graphs. J. Combin. Theory, Ser. B 62 (1994), 199-212. DOI 10.1006/jctb.1994.1064 | MR 1305048 | Zbl 0807.05020
[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. DOI 10.1109/TCS.1983.1085385 | MR 0715502
[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. DOI 10.1002/jgt.3190130606 | MR 1025892
[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
[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.
[12] M. Lewinter: Interpolation theorem for the number of degree-preserving vertices of spanning trees. IEEE Trans. Circuits Syst. CAS-34 (1987), 205. DOI 10.1109/TCS.1987.1086107 | MR 0874697
[13] Y. Lin: A simpler proof of interpolation theorem for spanning trees. Kexue Tongbao 30 (1985), 134. MR 0795526
[14] G. Liu: A lower bound on solutions of Chartrand’s problem. Applicatae Sinica 1 (1984), 93–96. DOI 10.1007/BF01883897 | Zbl 0577.05024
[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
[16] H. E. Robbins: A theorem on graphs, with an application to a problem of traffic control. Amer. Math. Monthly 46 (1939), 281–283. DOI 10.2307/2303897 | MR 1524589 | Zbl 0021.35703
[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
[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. DOI 10.1002/net.3230190204 | MR 0984567
[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. DOI 10.1002/net.3230220202 | MR 1148018
[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. DOI 10.1016/0166-218X(94)90217-8 | MR 1272496
[21] 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
[22] R. P. Stanley: Acyclic orientations of graphs. Discrete Math. 5 (1973), 171–178. DOI 10.1016/0012-365X(73)90108-8 | MR 0317988 | Zbl 0258.05113
[23] F. Zhang and Z. Chen: Connectivity of (adjacency) tree graphs. J. Xinjiang Univ. 4 (1986), 1–5. MR 0919491
[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
[25] S. 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
Search
Partner of
