Irregularity strength of dense graphs

✍ Scribed by Bill Cuckler; Felix Lazebnik

• Publisher: John Wiley and Sons
• Year: 2008
• Tongue: English
• Weight: 152 KB
• Volume: 58
• Category: Article
• ISSN: 0364-9024
• DOI: 10.1002/jgt.20313

✦ Synopsis

Abstract

Let G be a simple graph of order n with no isolated vertices and no isolated edges. For a positive integer w, an assignment f on G is a function f: E(G) → {1, 2,…, w}. For a vertex v, f(v) is defined as the sum f(e) over all edges e of G incident with v. f is called irregular, if all f(v) are distinct. The smallest w for which there exists an irregular assignment on G is called the irregularity strength of G, and it is denoted by s(G). We show that if the minimum degree δ (G) ≥ 10__n__^3/4^ log^1/4^ n, then s(G) ≤ 48 (n/δ) + 6. For these δ, this improves the magnitude of the previous best upper bound of Frieze et al. by a log n factor. It also provides an affirmative answer to a question of Lehel, whether for every α ∈ (0, 1), there exists a constant c = c( α) such that s(G) ≤ c for every graph G of order n with minimum degree δ(G) ≥ (1 − α)n. Specializing the argument for d‐regular graphs with d ≥ 10^4/3^ n^2/3^ log^1/3^ n, we prove that s(G) ≤ 48 (n/d) + 6. © 2008 Wiley Periodicals, Inc. J Graph Theory 58: 299–313, 2008