Résumé | It is well known that there are no emph{irregular graphs},
understood as simple graphs with pairwise distinct vertex degrees,
except the trivial $1$-vertex case.
A graph invariant called the emph{irregularity strength}
was thus introduced aiming at capturing a level of irregularity of a graph.
Suppose that given a graph $G = (V,E)$ we wish to construct a
multigraph with pairwise distinct vertex degrees of it by multiplying some of its edges.
The least $k$ so that we are able to achieve such goal using at most k copies of every edge is denoted by $s(G)$ and referred to as the irregularity strength of $G$.
Alternately one may consider (not necessarily proper) edge colourings $c: E o{1,2,ldots,k}$ with
$sum_{e
i u}c(e)
eqsum_{e
i v}c(e)$ for every pair of distinct vertices $u,v in V$. Then the least $k$
which permits defining a colouring $c$ with this feature equals $s(G)$.
Numerous papers have been devoted to study on this graph invariant since the middle 80's.
On the other hand, there are many emph{locally irregular graphs}, i.e.,
those whose only emph{adjacent} vertices are required to have distinct degrees.
Analogously as above one might also measure how far a given graph $G=(V,E)$ is from being locally irregular.
That is, how large $k$ is needed in order to define an edge colouring $c: E o{1,2,ldots,k}$ with
$sum_{e
i u}c(e)
eqsum_{e
i v}c(e)$ for every pair of adjacent vertices $u,v$ of $G$.
It is believed that already $k=3$ is sufficient for all graphs containing no isolated edges.
This suspicion is commonly referred to as the 1--2--3--Conjecture. |