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.

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