✦ LIBER ✦

The irregularity strength of tP3

✍ Scribed by Lael Kinch; Jenő Lehel

Publisher: Elsevier Science
Year: 1991
Tongue: English
Weight: 372 KB
Volume: 94
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(91)90309-p

No coin nor oath required. For personal study only.

✦ Synopsis

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 and exhibit infinitely many sequences attaining equality. We also show s(t) G I(19 -1)/71 + 1 for every t. As a corollary we obtain that the irregularity strength of the graph G = tP,, the disjoint union of t paths of length 3, is about 5n/7, where n = 3t is the order of G.

📜 SIMILAR VOLUMES

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

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

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

Irregularity strength of dense graphs

✍ R.J. Faudree; M.S. Jacobson; L. Kinch; J. Lehel 📂 Article 📅 1991 🏛 Elsevier Science 🌐 English ⚖ 832 KB

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

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