Irregularity strength of dense graphs (Q5905417)

Let \(G\) be a simple graph. Then positive integer weights can be assigned to the edges of \(G\) so that the weighted degrees of all vertices are distinct. An assignment of weights to the edges of \(G\) such that the weighted degrees of all vertices are distinct is called an irregular assignment of \(G\). The minimum of the largest weights over all irregular assignments of \(G\) is called the irregularity strength of \(G\). The authors determine the irregularity strength of certain unions of complete graphs. Moreover the irregularity strength of `dense' graphs is studied. In particular it is shown that if \(t\) is a fixed positive integer and if \(n\) is sufficiently large, then each graph of order \(n\) with minimum degree \(n-t\) has irregularity strength at most 3.