| Title:
|
On $\gamma $-labelings of oriented graphs (English) |
| Author:
|
Okamoto, Futaba |
| Author:
|
Zhang, Ping |
| Author:
|
Saenpholphat, Varaporn |
| Language:
|
English |
| Journal:
|
Mathematica Bohemica |
| ISSN:
|
0862-7959 (print) |
| ISSN:
|
2464-7136 (online) |
| Volume:
|
132 |
| Issue:
|
2 |
| Year:
|
2007 |
| Pages:
|
185-203 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| 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. (English) |
| Keyword:
|
oriented graph |
| Keyword:
|
$\gamma $-labeling |
| Keyword:
|
balanced $\gamma $-labeling |
| Keyword:
|
balanced oriented graph |
| Keyword:
|
orientably balanced graph |
| MSC:
|
05C20 |
| MSC:
|
05C78 |
| idZBL:
|
Zbl 1174.05056 |
| idMR:
|
MR2338805 |
| DOI:
|
10.21136/MB.2007.134191 |
| . |
| Date available:
|
2009-09-24T22:30:43Z |
| Last updated:
|
2020-07-29 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/134191 |
| . |
| Reference:
|
[1] G. Chartrand, D. Erwin, D. W. VanderJagt, P. Zhang: $\gamma $-labelings of graphs.Bull. Inst. Combin. Appl. 44 (2005), 51–68. MR 2139387 |
| Reference:
|
[2] G. Chartrand, D. Erwin, D. W. VanderJagt, P. Zhang: On $\gamma $-labelings of trees.Discuss. Math., Graph Theory 25 (2005), 363–383. MR 2233002, 10.7151/dmgt.1289 |
| Reference:
|
[3] G. Chartrand, P. Zhang: Introduction to Graph Theory.McGraw-Hill, Boston, 2005. |
| Reference:
|
[4] J. A. Gallian,: A dynamic survey of graph labeling.Electron. J. Combin. 5 (1998), Dynamic Survey 6, pp. 43. Zbl 0953.05067, MR 1668059 |
| Reference:
|
[5] S. W. Golomb: How to number a graph.Graph Theory Comp. Academic Press, New York, 1972, pp. 23–37. Zbl 0293.05150, MR 0340107 |
| Reference:
|
[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. Zbl 0193.53204, MR 0223271 |
| . |
