Discussiones Mathematicae Graph Theory 30(1) (2010) 45-54
doi: 10.7151/dmgt.1475

[BIBTex] [PDF] [PS]

γ-Labelings of Complete Bipartite Graphs

Grady D. Bullington, Linda L. Eroh, Steven J. Winters

Department of Mathematics
University of Wisconsin Oshkosh
Oshkosh, Wisconsin 54901, USA


Explicit formulae for the γ-min and γ-max labeling values of complete bipartite graphs are given, along with γ-labelings which achieve these extremes. A recursive formula for the γ-min labeling value of any complete multipartite is also presented.

Keywords: γ-labelings, bipartite graphs, multipartite graphs.

2010 Mathematics Subject Classification: 05C78.


[1] G. Chartrand, D. Erwin, D.W. VanderJagt and P. Zhang, γ-labelings of graphs, Bull. Inst. Combin. Appl. 44 (2005) 51-68.
[2] G. Chartrand, D. Erwin, D. VanderJagt and P. Zhang, γ-labelings of trees, Discuss. Math. Graph Theory 25 (2005) 363-383, doi: 10.7151/dmgt.1289.
[3] C.M. da Fonseca, V. Saenpholphat and P. Zhang, The γ-spectrum of a graph, Ars. Combin., to appear.
[4] V. Saenpholphat, F. Okamoto and P. Zhang, On γ-labelings on oriented graphs, Math. Bohem. 132 (2007) 185-203.

Received 10 September 2008
Revised 29 December 2008
Accepted 14 January 2009