DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

https://doi.org/10.7151/dmgt

Discussiones Mathematicae Graph Theory

IMPACT FACTOR 2018: 0.741

SCImago Journal Rank (SJR) 2018: 0.763

Rejection Rate (2018-2019): c. 84%

Discussiones Mathematicae Graph Theory

PDF

Discussiones Mathematicae Graph Theory 25(3) (2005) 363-383
DOI: 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
valmax(G) = max { val(f) : f is a γ− labeling of G};
while the minimum value of a γ-labeling of G is
valmin(G) = min { val(f) : f is a γ− labeling of G};

The values valmax(Sp,q) and valmin(Sp,q) are determined for double stars Sp,q. We present characterizations of connected graphs G of order n for which valmin(G) = n or valmin(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