TY - JOUR

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

AU - Zhang, Fuji

AU - Chen, Zhibo

N1 - Funding Information:
1 Supported by the National Science Foundation of China 2 Sxipportedin part by the RDG grant of the Pennsylvania State University,USA

PY - 1998

Y1 - 1998

N2 - 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 O1 and O2 of G, |f(O1) - f(O2)| ≤ 1 whenever O1 and O2 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 O1 and O2 of G with f(O1) = p and f(O2) = 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 arcconnectivity and the absorption number, etc., have the above interpolation property on the set of all orientations of G.

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 O1 and O2 of G, |f(O1) - f(O2)| ≤ 1 whenever O1 and O2 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 O1 and O2 of G with f(O1) = p and f(O2) = 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 arcconnectivity and the absorption number, etc., have the above interpolation property on the set of all orientations of G.

UR - http://www.scopus.com/inward/record.url?scp=0033478939&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0033478939&partnerID=8YFLogxK

U2 - 10.1023/A:1022471626622

DO - 10.1023/A:1022471626622

M3 - Article

AN - SCOPUS:0033478939

SN - 0011-4642

VL - 48

SP - 433

EP - 438

JO - Czechoslovak Mathematical Journal

JF - Czechoslovak Mathematical Journal

IS - 3

ER -