PDF

Discussiones Mathematicae Graph Theory 25(3) (2005) 363-383
DOI: https://doi.org/10.7151/dmgt.1289

ON γ-LABELINGS OF TREES

Gary Chartrand Department of Mathematics Western Michigan University Kalamazoo, MI 49008 USA

David Erwin School of Mathematical Sciences University of KwaZulu-Natal Durban 4041, South Africa

Donald W. VanderJagt Department of Mathematics Grand Valley State University Allendale, MI 49401 USA

Ping Zhang Department of Mathematics Western Michigan University Kalamazoo, MI 49008 USA

Abstract

Let G be a graph of order n and size m. A γ-labeling of G is a one-to-one function f:V(G)→{0,1,2,...,m} that induces a labeling f ^':E(G)→{1,2,...,m} of the edges of G defined by f ^'(e) = |f(u)-f(v)| for each edge e = uv of G. The value of a γ-labeling f is val(f) = Σ_{e ∈ E(G)}f ^'(e). The maximum value of a γ-labeling of G is defined as val_max(G) = max { val(f) : f is a γ− labeling of G}; while the minimum value of a γ-labeling of G is val_min(G) = min { val(f) : f is a γ− labeling of G};

The values val_max(S_p,q) and val_min(S_p,q) are determined for double stars S_p,q. We present characterizations of connected graphs G of order n for which val_min(G) = n or val_min(G) = n+1.

Keywords: γ-labeling, value of a γ-labeling.

2000 Mathematics Subject Classification: 05C78, 05C05.

References

[1]	G. Chartrand, D. Erwin, D.W. VanderJagt and P. Zhang, γ-Labelings of graphs, Bull. Inst. Combin. Appl. 44 (2005) 51-68.
[2]	J.A. Gallian, A dynamic survey of graph labeling, Electron. J. Combin. #DS6 (Oct. 2003 Version).
[3]	S.M. Hegde, On (k,d)-graceful graphs, J. Combin. Inform. System Sci. 25 (2000) 255-265.

Received 16 April 2004
Revised 6 November 2004