×

\(\gamma\)-labelings of graphs. (English) Zbl 1074.05079

A \(\gamma\)-labeling of a graph \(G=(V,E)\) is a one-to-one function \(f:V\mapsto\{0,1,\dots,| E| \}\). This vertex labeling induces an edge labeling \(f'\) defined by \(f'(e)=| f(u)-f(v)| \) for each edge \(e=uv\in E\). The value of the \(\gamma\)-labeling \(f\) is the number \(\text{ val}(f)=\sum_{e\in E} f'(e)\).
The authors compute the minimum and the maximum for the value of the \(\gamma\)-labelings for paths, cycles, and complete graphs and the maximum for connected regular bipartite graphs. They also provide a lower bound for the minimum of the value of the form \({k+1\choose 2}(| V| + (k+2)/3) + (| E| - | V| k)(k+1)\), where \(k= \max\{s\leq n-1\bigm| \sum^s_{i=1} (| V| -i) \leq | E| \}\).

MSC:

05C78 Graph labelling (graceful graphs, bandwidth, etc.)
05C38 Paths and cycles
PDFBibTeX XMLCite