Edge-injective and edge-surjective vertex labellings

Brandt, Stephan; Miskuf, Jozef; Rautenbach, Dieter GND; Regen, Friedrich GND

For a graph G = (V,E) we consider vertex-k-labellings f : V \rightarrow {1,2,...,k} for which the induced edge weighting w : E \rightarrow {2,3,..., 2k} with w(uv) = f(u) + f(v) is injective or surjective or both. We study the relation between these labellings and the number theoretic notions of an additive basis and a Sidon set, present a new construction for a so-called restricted additive basis and derive the corresponding consequences for the labellings. We prove that a tree of order n and maximum degree \triangle has a vertex-k-labelling f for which w is bijective if and only if \triangle \leq k = n/2. Using this result we prove a recent conjecture of Ivančo and Jendrol' concerning edge-irregular total labellings for graphs that are sparse enough.


Citation style:

Brandt, Stephan / Miskuf, Jozef / Rautenbach, Dieter / et al: Edge-injective and edge-surjective vertex labellings. 2008.

Access Statistic

Last 12 Month:

open graphic


Use and reproduction:
All rights reserved