Edge irregular total labellings for graphs of linear size |
| |
Authors: | Stephan Brandt |
| |
Affiliation: | a Institut für Mathematik, TU Ilmenau, Postfach 100565, D-98684 Ilmenau, Germany b Institute of Mathematics, Faculty of Science, University of Pavol Jozef Šafarik, 040 01 Košice, Slovak Republic |
| |
Abstract: | As an edge variant of the well-known irregularity strength of a graph G=(V,E) we investigate edge irregular total labellings, i.e. functions f:V∪E→{1,2,…,k} such that f(u)+f(uv)+f(v)≠f(u′)+f(u′v′)+f(v′) for every pair of different edges uv,u′v′∈E. The smallest possible k is the total edge irregularity strength of G. Confirming a conjecture by Ivan?o and Jendrol’ for a large class of graphs we prove that the natural lower bound is tight for every graph of order n, size m and maximum degree Δ with m>111000Δ. This also implies that the probability that a random graph from G(n,p(n)) satisfies the Ivan?o-Jendrol’ Conjecture tends to 1 as n→∞ for all functions p∈[0,1]N. Furthermore, we prove that is an upper bound for every graph G of order n and size m≥3 whose edges are not all incident to a single vertex. |
| |
Keywords: | Edge irregular total labelling Total edge irregularity strength Irregular assignment Irregularity strength |
本文献已被 ScienceDirect 等数据库收录! |
|