Irregular Assignments and Two Problems à la Ringel

One of the best-known facts in graph theory states that any (simple) graph with at least two vertices contains two vertices of the same degree. Hence the following problem, initiated in [5], arises: Consider a weighting w: E(G) → {1,..., m} and denote by $$w(v)=\sum\limits_{\ell \in e}{w(e)}$$ the weighted degree of the vertex υ ∈ V. We call the weighting w admissible or an irregular assignment if all weighted degrees are distinct. What is the minimum number m for which an admissible weighting exists? This number s(G) is called the irregularity strength of G. Our observation above shows s(G) ≥ 2 for any graph G, and it is an easy exercise to show that s(G) < ∞ iff G has no isolated edge and at most one isolated vertex.