Szczegóły publikacji
Opis bibliograficzny
Linear bound on the irregularity strength and the total vertex irregularity strength of graphs / Jakub PRZYBYŁO // SIAM Journal on Discrete Mathematics ; ISSN 0895-4801 . — 2009 — vol. 23 no. 1, s. 511–516. — Bibliogr. s. 516, Abstr.
Autor
Słowa kluczowe
Dane bibliometryczne
| ID BaDAP | 43250 |
|---|---|
| Data dodania do BaDAP | 2009-02-04 |
| Tekst źródłowy | URL |
| DOI | 10.1137/070707385 |
| Rok publikacji | 2009 |
| Typ publikacji | artykuł w czasopiśmie |
| Otwarty dostęp |  |
| Czasopismo/seria | SIAM Journal on Discrete Mathematics |
Abstract
Let G be a simple graph of order n with no isolated edges and at most one isolated vertex. For a positive integer w, a w-weighting of G is a function f : E(G) → {1, 2, . . . ,w}. An irregularity strength of G, s(G), is the smallest w such that there is a w-weighting of G for which Σ e:u∈e f(e) ≠ Σe:v∈e f(e) for all pairs of different vertices u, v ∈ V (G). We prove that s(G) < 112 n/δ + 28, where δ is the minimum degree of G. For d-regular graphs, we strengthen this to s(G) < 40 n/d +11. These upper bounds represent improvements of many existing ones. Similar results concerning the "total" version of the irregularity strength are also discussed. © 2008 Society for Industrial and Applied Mathematics.
