✦ LIBER ✦

On the irregularity strength of trees

✍ Scribed by Tom Bohman; David Kravitz

Publisher: John Wiley and Sons
Year: 2004
Tongue: English
Weight: 126 KB
Volume: 45
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.10158

No coin nor oath required. For personal study only.

✦ Synopsis

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 actual irregularity strength up to an additive constant. In fact, this was conjectured to be the truth for regular graphs and for trees. Here we find an infinite sequence of trees with λ(T) = n~1~ but strength converging to ${11-\sqrt 5\over 8} n_1$. © 2004 Wiley Periodicals, Inc. J Graph Theory 45: 241–254, 2004

📜 SIMILAR VOLUMES

On graph irregularity strength

✍ Alan Frieze; Ronald J. Gould; Michał Karoński; Florian Pfender 📂 Article 📅 2002 🏛 John Wiley and Sons 🌐 English ⚖ 132 KB

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

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 irregularities of distribution, II

✍ K. F. Roth 📂 Article 📅 1976 🏛 John Wiley and Sons 🌐 English ⚖ 220 KB

On Irregularities of Distribution IV

✍ W.W.L Chen 📂 Article 📅 2000 🏛 Elsevier Science 🌐 English ⚖ 148 KB

Here the case W=2 was established by Roth [11,12]. The general case was established by Schmidt [13] and Chen [6]. Note also that the conclusions remain true in the trivial case L=1.

Irregularity and the period determinant

Irregularity and the period determinant for irregular singular connections on surfaces

✍ M. Hien 📂 Article 📅 2010 🏛 John Wiley and Sons 🌐 English ⚖ 284 KB

## Abstract In [6], we constructed a period pairing for flat irregular singular conncetions on surfaces. We now extend these constructions to a perfect period pairing between the irregularity complex of the connection and the complex of relative rapid decay chains. As a consequence, the period dete

On the profile of random trees

✍ Michael Drmota; Bernhard Gittenberger 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 302 KB 👁 2 views

Let T be a plane rooted tree with n nodes which is regarded as family tree of a Galton-Watson branching process conditioned on the total progeny. The profile of the tree ' may be described by the number of nodes or the number of leaves in layer t n , respectively. It is shown that these two processe