On the Irregularity Strength of Dense Graphs
Piotr Majerski, Jakub Przybyło · SIAM Journal on Discrete Mathematics · 2014
Consider a graph $G=(V,E)$ of minimum degree $\delta$ and order $n$. Its irregularity strength is the smallest integer $k$ for which one can find a weighting $w:E\to \{1,2,\ldots,k\}$ such that $\sum_{e i u}w(e) eq \sum_{e i v}w(e)$ for every pair $u,v$ of vertices of $G$. In other words, it is just the maximum edge multiplicity required in an irregular multigraph whose underlying graph is $G$. We prove that the irregularity strength of graphs with $\delta\geq n^{0.5}\ln n$ is bounded from above by $(4+o(1))\frac{n}{\delta}+4$. Our approach is based on a random ordering of the vertices of a graph suitable for applying a development of the algorithm used by Kalkowski, Karoński, and Pfender to prove the bound of $6\left\lceil\frac{n}{\delta}\right\rceil$ for $\delta\geq 1$, which is the best upper bound thus far.