Szczegóły publikacji
Opis bibliograficzny
On the irregularity strength of dense graphs / Piotr MAJERSKI, Jakub PRZYBYŁO // SIAM Journal on Discrete Mathematics ; ISSN 0895-4801. — 2014 — vol. 28 no. 1, s. 197–205. — Bibliogr. s. 204–05, Abstr.
Autorzy (2)
Słowa kluczowe
Dane bibliometryczne
| ID BaDAP | 80775 |
|---|---|
| Data dodania do BaDAP | 2014-03-26 |
| Tekst źródłowy | URL |
| DOI | 10.1137/120886650 |
| Rok publikacji | 2014 |
| Typ publikacji | artykuł w czasopiśmie |
| Otwarty dostęp |  |
| Czasopismo/seria | SIAM Journal on Discrete Mathematics |
Abstract
Consider a graph G = (V, E) of minimum degree delta and order n. Its irregularity strength is the smallest integer k for which one can find a weighting w : E -> {1, 2,..., k} such that Sigma(e(sic)u) w(e) not equal Sigma(e(sic)v) w(e) for every pair u, v of vertices of G. In other words, it is just the maximum edge multiplicity required in an irregular multigraph whose underlying graph is G. We prove that the irregularity strength of graphs with delta >= n(0.5) ln n is bounded from above by (4+ o(1))n/delta + 4. Our approach is based on a random ordering of the vertices of a graph suitable for applying a development of the algorithm used by Kalkowski, Karonski, and Pfender to prove the bound of 6 inverted right perpendicularn/delta inverted left perpendicular for delta >= 1, which is the best upper bound thus far.
