𝔖 Bobbio Scriptorium
✦   LIBER   ✦

The irregularity strength and cost of the union of cliques

✍ Scribed by Stanislav Jendroľ; Michal Tkáč; Zsolt Tuza

Publisher
Elsevier Science
Year
1996
Tongue
English
Weight
333 KB
Volume
150
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

✦ Synopsis

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 the vertex-disjoint union of complete graphs is determined. The method of proof also yields the smallest possible total increase in the sum of edge weights in irregular asignments, called irregularity cost.

📜 SIMILAR VOLUMES

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

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

On the irregularity strength of the m ×
On the irregularity strength of the m × n grid
✍ Jeffrey H. Dinitz; David K. Garnick; Andras Gyárfás 📂 Article 📅 1992 🏛 John Wiley and Sons 🌐 English ⚖ 939 KB

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