On $\gamma $-labelings of oriented graphs

Okamoto, Futaba ; Zhang, Ping ; Saenpholphat, Varaporn

Mathematica Bohemica, Tome 132 (2007) no. 2, pp. 185-203.

Résumé

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 \lbrace 0, 1, 2, \ldots , m\rbrace $ that induces a labeling $f^{\prime }\: E(D) \rightarrow \lbrace \pm 1, \pm 2, \ldots , \pm m\rbrace $ of the arcs of $D$ defined by $f^{\prime }(e) = f(v)-f(u)$ for each arc $e =(u, v)$ of $D$. The value of a $\gamma $-labeling $f$ is $\mathop {\mathrm val}(f) = \sum _{e \in E(G)} f^{\prime }(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 \ge 2$ is orientably balanced unless $G$ is a tree, $n \equiv 2 \hspace{4.44443pt}(\@mod \; 4)$, and every vertex of $G$ has odd degree.

Détail

DOI : 10.21136/MB.2007.134191

Classification : 05C20, 05C78
Keywords: oriented graph; $\gamma $-labeling; balanced $\gamma $-labeling; balanced oriented graph; orientably balanced graph