𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On a conjecture about edge irregular total labelings

✍ Scribed by Stephan Brandt; Jozef Miškuf; Dieter Rautenbach

Publisher
John Wiley and Sons
Year
2008
Tongue
English
Weight
131 KB
Volume
57
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

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 $\Delta < {{{10}}^{-{{3}}}{{m}}\over \sqrt{{{8}}{{n}}}}$ there is a mapping ${{f}}:{{V}}\cup {{E}}\to \big{{{1}},{{2}},\ldots,\big\lceil{{{m}}+{{2}}\over {{3}}}\big\rceil\big}$ such that ${{f}}({{u}})+{{f}}({{uv}})+{{f}}({{v}})\not={{f}}({{u}}')+{{f}}({{u}}'{{v}}')+{{f}}({{v}}')$ for every ${{uv}},{{u}}'{{v}}'\in {{E}}$ with ${{uv}}\not={{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. © 2008 Wiley Periodicals, Inc. J Graph Theory 57: 333–343, 2008

📜 SIMILAR VOLUMES

On a Conjecture of Nicolas–Sárközy about
On a Conjecture of Nicolas–Sárközy about Partitions
✍ F. Ben saı̈d 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 152 KB

Let N be the set of positive integers, B ¼ fb 1 5 . . . 5b k g & N, N 2 N, and N5b k . For i ¼ 0 or 1, A ¼ A i ðB; NÞ is the set (introduced by Nicolas, Ruzsa, and Sa´rko¨zy, J. Number Theory 73 (1998), 292-317) such that A \ f1; . . . ; Ng ¼ B and pðA; nÞ iðmod2Þ for n 2 N; n4N, where pðA; nÞ denot

On a conjecture about the generalized ex
On a conjecture about the generalized exponent of primitive matrices
✍ Bolian Liu; Qiaoliang Li 📂 Article 📅 1994 🏛 John Wiley and Sons 🌐 English ⚖ 122 KB

## Abstract In this paper the conjecture on the __k__th upper multiexponent of primitive matrices proposed by R.A. Brualdi and Liu are completely proved.

On a Conjecture about Trees in Graphs wi
On a Conjecture about Trees in Graphs with Large Girth
✍ Tao Jiang 📂 Article 📅 2001 🏛 Elsevier Science 🌐 English ⚖ 169 KB

The girth of a graph G is the length of a shortest cycle in G. Dobson (1994, Ph.D. dissertation, Louisiana State University, Baton Rouge, LA) conjectured that every graph G with girth at least 2t+1 and minimum degree at least kÂt contains every tree T with k edges whose maximum degree does not excee

A note on a conjecture about cycles with
A note on a conjecture about cycles with many incident chords
✍ Tao Jiang 📂 Article 📅 2004 🏛 John Wiley and Sons 🌐 English ⚖ 44 KB

## Abstract Given positive integers __n__ and __k__, let __g__~__k__~(__n__) denote the maximum number of edges of a graph on __n__ vertices that does not contain a cycle with __k__ chords incident to a vertex on the cycle. Bollobás conjectured as an exercise in [2, p. 398, Problem 13] that there e