Futaba Okamoto, University of Wisconsin-La Crosse, Mathematics Department, La Crosse, WI 5461, USA; Ping Zhang, Western Michigan University, Department of Mathematics, Kalamazoo, MI 49008, USA, e-mail: ping.zhang@wmich.edu; Varaporn Saenpholphat, Srinakharinwirot University, Department of Mathematics, Sukhumvit Soi 23, Bangkok, 10110, Thailand
Abstract: Let $D$ be an oriented graph of order $n$ and size $m$. A $\ga $-labeling of $D$ is a one-to-one function $f V(D) \rightarrow \{0, 1, 2, \ldots , m\}$ that induces a labeling $f' E(D) \rightarrow \{\pm 1, \pm 2, \ldots , \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 $\ga $-labeling $f$ is $\val (f) = \sum _{e \in E(G)} f'(e).$ A $\ga $-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 \ge 2$ is orientably balanced unless $G$ is a tree, $n \equiv 2 \pmod 4$, and every vertex of $G$ has odd degree.
Keywords: oriented graph, $\ga $-labeling, balanced $\ga $-labeling, balanced oriented graph, orientably balanced graph
Classification (MSC2000): 05C20, 05C78
Full text of the article: