Interpolation theorem for a continuous function on orientations of a simple graph

Fu Ji Zhang; Zhibo Chen

Czechoslovak Mathematical Journal (1998)

  • Volume: 48, Issue: 3, page 433-438
  • ISSN: 0011-4642

Abstract

top
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 ) | ≤ 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 .

How to cite

top

Zhang, Fu Ji, and Chen, Zhibo. "Interpolation theorem for a continuous function on orientations of a simple graph." Czechoslovak Mathematical Journal 48.3 (1998): 433-438. <http://eudml.org/doc/30431>.

@article{Zhang1998,
abstract = {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$.},
author = {Zhang, Fu Ji, Chen, Zhibo},
journal = {Czechoslovak Mathematical Journal},
keywords = {orientation of a graph; interpolation property; connectivity; arboricity},
language = {eng},
number = {3},
pages = {433-438},
publisher = {Institute of Mathematics, Academy of Sciences of the Czech Republic},
title = {Interpolation theorem for a continuous function on orientations of a simple graph},
url = {http://eudml.org/doc/30431},
volume = {48},
year = {1998},
}

TY - JOUR
AU - Zhang, Fu Ji
AU - Chen, Zhibo
TI - Interpolation theorem for a continuous function on orientations of a simple graph
JO - Czechoslovak Mathematical Journal
PY - 1998
PB - Institute of Mathematics, Academy of Sciences of the Czech Republic
VL - 48
IS - 3
SP - 433
EP - 438
AB - 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$.
LA - eng
KW - orientation of a graph; interpolation property; connectivity; arboricity
UR - http://eudml.org/doc/30431
ER -

References

top
  1. 10.1016/0012-365X(84)90061-X, Discrete Math. 49 (1984), 109–112. (1984) Zbl0576.05057MR0740426DOI10.1016/0012-365X(84)90061-X
  2. 10.1007/BF01669670, Acta Math. Applicatae Sinica 1 (1984), 97–98. (1984) Zbl0574.05014DOI10.1007/BF01669670
  3. Theory and Applications of Graphs, Wiley, New York, 1980. (1980) MR0634511
  4. Graphs & Digraphs, 2nd. ed., Wadsworth & Brookds, Monterey, California, 1986. (1986) MR0834583
  5. 10.1016/0095-8956(78)90078-3, J. Combin. Theory, Ser. B 24 (1978), 61–75. (1978) MR0491326DOI10.1016/0095-8956(78)90078-3
  6. 10.1137/0406003, SIAM J. Discrete Math. 6 (1993), 30–43. (1993) MR1201988DOI10.1137/0406003
  7. 10.1006/jctb.1994.1064, J. Combin. Theory, Ser. B 62 (1994), 199-212. (1994) Zbl0807.05020MR1305048DOI10.1006/jctb.1994.1064
  8. 10.1109/TCS.1983.1085385, IEEE Trans. Circuits Syst. CAS-30 (1983), 429–431. (1983) MR0715502DOI10.1109/TCS.1983.1085385
  9. 10.1002/jgt.3190130606, J. Graph Theory 13 (1989), 703–712. (1989) MR1025892DOI10.1002/jgt.3190130606
  10. Interpolation theorems for the independence and domination numbers of spanning trees, Graph Theory in Memory of G. A. Dirac, to appear. MR0976003
  11. 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. 10.1109/TCS.1987.1086107, IEEE Trans. Circuits Syst. CAS-34 (1987), 205. (1987) MR0874697DOI10.1109/TCS.1987.1086107
  13. A simpler proof of interpolation theorem for spanning trees, Kexue Tongbao 30 (1985), 134. (1985) MR0795526
  14. 10.1007/BF01883897, Applicatae Sinica 1 (1984), 93–96. (1984) Zbl0577.05024DOI10.1007/BF01883897
  15. 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. (1979) MR0538032
  16. 10.2307/2303897, Amer. Math. Monthly 46 (1939), 281–283. (1939) Zbl0021.35703MR1524589DOI10.2307/2303897
  17. On the optimal strongly connected operations of city street graphs I: Large grids, SIAM J. Discrete Math. 1 (1988), 199–222. (1988) MR0941351
  18. 10.1002/net.3230190204, Networks 19 (1989), 221–233. (1989) MR0984567DOI10.1002/net.3230190204
  19. 10.1002/net.3230220202, Networks 22 (1992), 109–143. (1992) MR1148018DOI10.1002/net.3230220202
  20. 10.1016/0166-218X(94)90217-8, Discrete Appl. Math. 49 (1994), 331–356. (1994) MR1272496DOI10.1016/0166-218X(94)90217-8
  21. 10.1002/jgt.3190070209, J. Graph Theory 7 (1983), 203–208. (1983) Zbl0482.05032MR0698702DOI10.1002/jgt.3190070209
  22. 10.1016/0012-365X(73)90108-8, Discrete Math. 5 (1973), 171–178. (1973) Zbl0258.05113MR0317988DOI10.1016/0012-365X(73)90108-8
  23. Connectivity of (adjacency) tree graphs, J. Xinjiang Univ. 4 (1986), 1–5. (1986) MR0919491
  24. 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. (1985) MR0918861
  25. 10.1016/0012-365X(95)91429-T, Discrete Math. 137 (1995), 395–397. (1995) Zbl0812.05065MR1312476DOI10.1016/0012-365X(95)91429-T

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.