z-logo
Premium
Irregularity strength of dense graphs
Author(s) -
Cuckler Bill,
Lazebnik Felix
Publication year - 2008
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.20313
Subject(s) - combinatorics , mathematics , graph , vertex (graph theory) , simple graph , upper and lower bounds , order (exchange) , degree (music) , integer (computer science) , discrete mathematics , physics , mathematical analysis , finance , computer science , acoustics , economics , programming language
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

This content is not available in your region!

Continue researching here.

Having issues? You can contact us here