𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On graph irregularity strength

✍ Scribed by Alan Frieze; Ronald J. Gould; Michał Karoński; Florian Pfender

Publisher
John Wiley and Sons
Year
2002
Tongue
English
Weight
132 KB
Volume
41
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

An assignment of positive integer weights to the edges of a simple graph G is called irregular, if the weighted degrees of the vertices are all different. The irregularity strength, s(G), is the maximal weight, minimized over all irregular assignments. In this study, we show that s(G) ≤ c~1~ n/δ, for graphs with maximum degree Δ ≤ n^1/2^ and minimum degree δ, and s(G) ≤ c~2~(log n)n/δ, for graphs with Δ > n^1/2^, where c~1~ and c~2~ are explicit constants. To prove the result, we are using a combination of deterministic and probabilistic techniques. © 2002 Wiley Periodicals, Inc. J Graph Theory 41: 120–137, 2002

📜 SIMILAR VOLUMES

Irregularity strength of dense graphs
Irregularity strength of dense graphs
✍ Bill Cuckler; Felix Lazebnik 📂 Article 📅 2008 🏛 John Wiley and Sons 🌐 English ⚖ 152 KB

## 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

On the irregularity strength of trees
On the irregularity strength of trees
✍ Tom Bohman; David Kravitz 📂 Article 📅 2004 🏛 John Wiley and Sons 🌐 English ⚖ 126 KB

## Abstract For any graph __G__, let __n~i~__ be the number of vertices of degree __i__, and $\lambda (G)={max} \_{i\le j}\{ {n\_i+\cdots +n\_j+i-1\over j}\}$. This is a general lower bound on the irregularity strength of graph __G__. All known facts suggest that for connected graphs, this is the a

How local irregularity gets global in a
How local irregularity gets global in a graph
✍ Dieter Rautenbach; Lutz Volkmann 📂 Article 📅 2002 🏛 John Wiley and Sons 🌐 English ⚖ 66 KB

## Abstract We prove asymptotically tight bounds on the difference between the maximum degree and the minimum degree of a simple graph in terms of its order and of the maximum difference between the degrees of adjacent vertices. Examples showing tightness and a conjecture are presented. © 2002 Wile

The size of strength-maximal graphs
The size of strength-maximal graphs
✍ Hong-Jian Lai 📂 Article 📅 1990 🏛 John Wiley and Sons 🌐 English ⚖ 381 KB

## Abstract Let __G__ be a graph and let __k__′(__G__) be the edge‐connectivity of __G__. The __strength__ of __G__, denoted by k̄′(__G__), is the maximum value of __k__′(__H__), where __H__ runs over all subgraphs of __G__. A simple graph __G__ is called k‐__maximal__ if k̄′(__G__) ≤ __k__ but for