Article
Full entry |
PDF
(0.3 MB)
Feedback
PDF
(0.3 MB)
Feedback
Keywords:
oriented graph; $\gamma $-labeling; balanced $\gamma $-labeling; balanced oriented graph; orientably balanced graph
oriented graph; $\gamma $-labeling; balanced $\gamma $-labeling; balanced oriented graph; orientably balanced graph
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 \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.
References:
[1] G. Chartrand, D. Erwin, D. W. VanderJagt, P. Zhang: $\gamma $-labelings of graphs. Bull. Inst. Combin. Appl. 44 (2005), 51–68. MR 2139387
[2] G. Chartrand, D. Erwin, D. W. VanderJagt, P. Zhang: On $\gamma $-labelings of trees. Discuss. Math., Graph Theory 25 (2005), 363–383. DOI 10.7151/dmgt.1289 | MR 2233002
[3] G. Chartrand, P. Zhang: Introduction to Graph Theory. McGraw-Hill, Boston, 2005.
[4] J. A. Gallian,: A dynamic survey of graph labeling. Electron. J. Combin. 5 (1998), Dynamic Survey 6, pp. 43. MR 1668059 | Zbl 0953.05067
[5] S. W. Golomb: How to number a graph. Graph Theory Comp. Academic Press, New York, 1972, pp. 23–37. MR 0340107 | Zbl 0293.05150
[6] A. Rosa: On certain valuations of the vertices of a graph. Theory Graphs, Proc. Int. Symp. Rome 1966, Gordon and Breach, New York, 1967, pp. 349–355. MR 0223271 | Zbl 0193.53204
Search
Partner of
