# zbMATH — the first resource for mathematics

On $$\gamma$$-labelings of oriented graphs. (English) Zbl 1174.05056
Summary: Let $$D$$ be an oriented graph of order $$n$$ and size $$m$$. A $$\gamma$$-labeling of $$D$$ is a one-to-one function $$f\: V(D) \rightarrow \{0, 1, 2, \dots , m\}$$ that induces a labeling $$f'\: E(D) \rightarrow \{\pm 1, \pm 2, \dots , \pm m\}$$ of the arcs of $$D$$ defined by $$f'(e) = f(v)-f(u)$$ for each arc $$e =(u, v)$$ of $$D$$. The value of a $$\gamma$$-labeling $$f$$ is $$\operatorname {val} (f) = \sum _{e \in E(G)} f'(e)$$. A $$\gamma$$-labeling of $$D$$ is balanced if the value of $$f$$ is 0. An oriented graph $$D$$ is balanced if $$D$$ has a balanced labeling. A graph $$G$$ is orientably balanced if $$G$$ has a balanced orientation. It is shown that a connected graph $$G$$ of order $$n \geq 2$$ is orientably balanced unless $$G$$ is a tree, $$n \equiv 2 \pmod 4$$, and every vertex of $$G$$ has odd degree.

##### MSC:
 05C20 Directed graphs (digraphs), tournaments 05C78 Graph labelling (graceful graphs, bandwidth, etc.)
Full Text: