LINEAR BOUND ON THE IRREGULARITY STRENGTH AND THE TOTAL VERTEX IRREGULARITY STRENGTH OF GRAPHS

摘要

Let G be a simple graph of order n with no isolated edges and at most one isolated vertex. For a positive integer w, a w-weighting of G is a function f : E(G) → {1, 2,..., w}. An irregularity strength of G, s(G), is the smallest w such that there is a w-weighting of G for which Σ_(e:u∈e) f(e) ≠ Σ_(e:v∈e) f(e) f(e) for all pairs of different vertices u,v ∈ V(G). We prove that s(G) ＜ 112n/δ + 28, where δ is the minimum degree of G. For d-regular graphs, we strengthen this to s(G) ＜ 40n/d + 11. These upper bounds represent improvements of many existing ones. Similar results concerning the "total" version of the irregularity strength are also discussed.