On a conjecture about edge irregular total labelings

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

Publikation: Bidrag til tidsskriftTidsskriftartikelForskningpeer review

Resumé

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

Maximum Degree
Labeling
Irregular
Graph in graph theory
Multigraph
Minimum Degree

Citer dette

Brandt, Stephan ; Rautenbach, D. ; Miškuf, J. / On a conjecture about edge irregular total labelings. I: Journal of Graph Theory. 2008 ; Bind 57, Nr. 4. s. 333-343.
@article{e215ecf7fa4e47298c890ead7456986b,
title = "On a conjecture about edge irregular total labelings",
abstract = "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.",
author = "Stephan Brandt and D. Rautenbach and J. Miškuf",
note = "Copyright 2008 Elsevier B.V., All rights reserved.",
year = "2008",
doi = "10.1002/jgt.20287",
language = "English",
volume = "57",
pages = "333--343",
journal = "Journal of Graph Theory",
issn = "0364-9024",
publisher = "JohnWiley & Sons, Inc.",
number = "4",

}

Brandt, S, Rautenbach, D & Miškuf, J 2008, 'On a conjecture about edge irregular total labelings', Journal of Graph Theory, bind 57, nr. 4, s. 333-343. https://doi.org/10.1002/jgt.20287

On a conjecture about edge irregular total labelings. / Brandt, Stephan; Rautenbach, D.; Miškuf, J.

I: Journal of Graph Theory, Bind 57, Nr. 4, 2008, s. 333-343.

Publikation: Bidrag til tidsskriftTidsskriftartikelForskningpeer review

TY - JOUR

T1 - On a conjecture about edge irregular total labelings

AU - Brandt, Stephan

AU - Rautenbach, D.

AU - Miškuf, J.

N1 - Copyright 2008 Elsevier B.V., All rights reserved.

PY - 2008

Y1 - 2008

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=42149134341&partnerID=8YFLogxK

U2 - 10.1002/jgt.20287

DO - 10.1002/jgt.20287

M3 - Journal article

AN - SCOPUS:42149134341

VL - 57

SP - 333

EP - 343

JO - Journal of Graph Theory

JF - Journal of Graph Theory

SN - 0364-9024

IS - 4

ER -