Geodesic
On $\gamma $-labelings of oriented graphs
Mathematica Bohemica, Tome 132 (2007) no. 2, pp. 185-203

Voir la notice de l'article provenant de la source Czech Digital Mathematics Library

MR Zbl
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.
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.
DOI : 10.21136/MB.2007.134191
Classification : 05C20, 05C78
Keywords: oriented graph; $\gamma $-labeling; balanced $\gamma $-labeling; balanced oriented graph; orientably balanced graph 
Okamoto, Futaba; Zhang, Ping; Saenpholphat, Varaporn. On $\gamma $-labelings of oriented graphs. Mathematica Bohemica, Tome 132 (2007) no. 2, pp. 185-203. doi: 10.21136/MB.2007.134191
@article{10_21136_MB_2007_134191,
     author = {Okamoto, Futaba and Zhang, Ping and Saenpholphat, Varaporn},
     title = {On $\gamma $-labelings of oriented graphs},
     journal = {Mathematica Bohemica},
     pages = {185--203},
     year = {2007},
     volume = {132},
     number = {2},
     doi = {10.21136/MB.2007.134191},
     mrnumber = {2338805},
     zbl = {1174.05056},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.21136/MB.2007.134191/}
}
TY  - JOUR
AU  - Okamoto, Futaba
AU  - Zhang, Ping
AU  - Saenpholphat, Varaporn
TI  - On $\gamma $-labelings of oriented graphs
JO  - Mathematica Bohemica
PY  - 2007
SP  - 185
EP  - 203
VL  - 132
IS  - 2
UR  - http://geodesic.mathdoc.fr/articles/10.21136/MB.2007.134191/
DO  - 10.21136/MB.2007.134191
LA  - en
ID  - 10_21136_MB_2007_134191
ER  - 
%0 Journal Article
%A Okamoto, Futaba
%A Zhang, Ping
%A Saenpholphat, Varaporn
%T On $\gamma $-labelings of oriented graphs
%J Mathematica Bohemica
%D 2007
%P 185-203
%V 132
%N 2
%U http://geodesic.mathdoc.fr/articles/10.21136/MB.2007.134191/
%R 10.21136/MB.2007.134191
%G en
%F 10_21136_MB_2007_134191

[1] G. Chartrand, D. Erwin, D. W. VanderJagt, P. Zhang: $\gamma $-labelings of graphs. Bull. Inst. Combin. Appl. 44 (2005), 51–68. | MR

[2] G. Chartrand, D. Erwin, D. W. VanderJagt, P. Zhang: On $\gamma $-labelings of trees. Discuss. Math., Graph Theory 25 (2005), 363–383. | DOI | MR

[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 | Zbl

[5] S. W. Golomb: How to number a graph. Graph Theory Comp. Academic Press, New York, 1972, pp. 23–37. | MR | Zbl

[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 | Zbl

Cité par Sources :