On a conjecture about edge irregular total labelings

Stephan Brandt, D. Rautenbach, J. Miškuf

Publikation: Bidrag til tidsskriftTidsskriftartikelForskningpeer review

Abstrakt

As our main result, we prove that for every multigraph G = (V, E) which has no loops and is of order n, size m, and maximum degree Δ <10 m/√n there is a mapping f : V ∩ E → {1, 2, . . . , ⌈m+2/3⌉} such that f(u) + f(uv) + f(v) ≠ f(u′) + f(u′ V′) + f(V′) for every uv, u′v′ ∈ E with uv ≠ u′V. Functions with this property were recently introduced and studied by Bača et al. and were called edge irregular total labelings. Our result confirms a recent conjecture of Ivančo and Jendrol' about such labelings for dense graphs, for graphs where the maximum and minimum degree are not too different in terms of the order, and also for large graphs of bounded maximum degree.
OriginalsprogEngelsk
TidsskriftJournal of Graph Theory
Vol/bind57
Udgave nummer4
Sider (fra-til)333-343
Antal sider11
ISSN0364-9024
DOI
StatusUdgivet - 2008

Fingeraftryk Dyk ned i forskningsemnerne om 'On a conjecture about edge irregular total labelings'. Sammen danner de et unikt fingeraftryk.

Citationsformater