𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On the irregularity strength of the m × n grid

✍ Scribed by Jeffrey H. Dinitz; David K. Garnick; Andras Gyárfás

Publisher
John Wiley and Sons
Year
1992
Tongue
English
Weight
939 KB
Volume
16
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

Given a graph G with weighting w: E(G) ← Z^+^, the Strength of G(w) is the maximum weight on any edge. The sum of a vertex in G(w) is the sum of the weights of all its incident edges. The network G(w) is irregular if the vertex sums are distinct. The irregularity strength of G is the minimum strength of the graph under all irregular weightings. In this paper we determine the irregularity strength of the m × n grid for certain m and n. In particular, for every positive integer d we find the irregularity strength for all but a finite number of m × n grids where n ‐ m = d. In addition, we present a general lower bound for the irregularity strength of graphs. © 1992 John Wiley & Sons, Inc.

📜 SIMILAR VOLUMES

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

The irregularity strength of tKp
The irregularity strength of tKp
✍ Stanislav Jendroľ; Michal Tkáč 📂 Article 📅 1995 🏛 Elsevier Science 🌐 English ⚖ 211 KB

Assign positive integer weights to the edges of a simple graph G (with no isolated edges and vertices) of order at least 3 in such a way that the graph becomes irregular, i.e. the weight sums at the vertices become pairwise distinct. The minimum of the largest weights assigned over all such irregula

The irregularity strength of tP3
The irregularity strength of tP3
✍ Lael Kinch; Jenő Lehel 📂 Article 📅 1991 🏛 Elsevier Science 🌐 English ⚖ 372 KB

Let (a,, . . . , a,, b,, . . . , b,) be the sequence of distinct positive integers such that ai + bi are distinct for i = 1, . . . , t, and different from ai and bj, 1 si s t. Denote by s(t) the minimum of the largest element of these sequences for fixed t. In this note we prove s(t) 2 [(15t -1)/71

The irregularity strength and cost of th
The irregularity strength and cost of the union of cliques
✍ Stanislav Jendroľ; Michal Tkáč; Zsolt Tuza 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 333 KB

Assign positive integer weights to the edges of a simple graph with no component isomorphic to Ki or 1£2, in such a way that the graph becomes irregular, i.e., the weight sums at the vertices become pairwise distinct. The minimum of the largest weights assigned over all such irregular assignments on