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

Zhang, Fuji ; Chen, Zhibo

Czechoslovak Mathematical Journal, Tome 48 (1998) no. 3, pp. 433-438.

Résumé

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$.

Détail

Classification : 05C20, 05C40