Geodesic
Interpolation theorem for a continuous function on orientations of a simple graph
Czechoslovak Mathematical Journal, Tome 48 (1998) no. 3, pp. 433-438 Cet article a éte moissonné depuis la source Czech Digital Mathematics Library

Voir la notice de l'article

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
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$, then for any integer $k$ such that $p$, 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$.
Classification : 05C20, 05C40 
@article{CMJ_1998_48_3_a4,
     author = {Zhang, Fuji and Chen, Zhibo},
     title = {Interpolation theorem for a continuous function on orientations of a simple graph},
     journal = {Czechoslovak Mathematical Journal},
     pages = {433--438},
     year = {1998},
     volume = {48},
     number = {3},
     mrnumber = {1637930},
     zbl = {0949.05034},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/CMJ_1998_48_3_a4/}
}
TY  - JOUR
AU  - Zhang, Fuji
AU  - Chen, Zhibo
TI  - Interpolation theorem for a continuous function on orientations of a simple graph
JO  - Czechoslovak Mathematical Journal
PY  - 1998
SP  - 433
EP  - 438
VL  - 48
IS  - 3
UR  - http://geodesic.mathdoc.fr/item/CMJ_1998_48_3_a4/
LA  - en
ID  - CMJ_1998_48_3_a4
ER  - 
%0 Journal Article
%A Zhang, Fuji
%A Chen, Zhibo
%T Interpolation theorem for a continuous function on orientations of a simple graph
%J Czechoslovak Mathematical Journal
%D 1998
%P 433-438
%V 48
%N 3
%U http://geodesic.mathdoc.fr/item/CMJ_1998_48_3_a4/
%G en
%F CMJ_1998_48_3_a4
Zhang, Fuji; Chen, Zhibo. Interpolation theorem for a continuous function on orientations of a simple graph. Czechoslovak Mathematical Journal, Tome 48 (1998) no. 3, pp. 433-438. http://geodesic.mathdoc.fr/item/CMJ_1998_48_3_a4/

[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 | MR | Zbl

[2] M. Cai: A solution of Chartrand’s problem on spanning trees. Acta Math. Applicatae Sinica 1 (1984), 97–98. | DOI | Zbl

[3] G. Chartrand et. al., eds.: Theory and Applications of Graphs. Wiley, New York, 1980. | MR

[4] G. Chartrand and L. Lesniak: Graphs & Digraphs, 2nd. ed. Wadsworth & Brookds, Monterey, California, 1986. | MR

[5] V. Chvátal and G. Thomassen: Distances in orientations of graphs. J. Combin. Theory, Ser. B 24 (1978), 61–75. | DOI | MR

[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 | MR

[7] A. M. H. Gerards: An orientation theorem for graphs. J. Combin. Theory, Ser. B 62 (1994), 199-212. | DOI | MR | Zbl

[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 | MR

[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 | MR

[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

[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 | MR

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

[14] G. Liu: A lower bound on solutions of Chartrand’s problem. Applicatae Sinica 1 (1984), 93–96. | DOI | Zbl

[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

[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 | MR | Zbl

[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

[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 | MR

[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 | MR

[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 | MR

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

[22] R. P. Stanley: Acyclic orientations of graphs. Discrete Math. 5 (1973), 171–178. | DOI | MR | Zbl

[23] F. Zhang and Z. Chen: Connectivity of (adjacency) tree graphs. J. Xinjiang Univ. 4 (1986), 1–5. | MR

[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

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