Szczegóły publikacji
Opis bibliograficzny
A generalization of Faudree–Lehel conjecture holds almost surely for random graphs / Jakub PRZYBYŁO // Random Structures & Algorithms ; ISSN 1042-9832. — 2022 — vol. 61 iss. 2, s. 383–396. — Bibliogr., Abstr. — Publikacja dostępna online od: 2021-11-07
Autor
Słowa kluczowe
Dane bibliometryczne
| ID BaDAP | 141274 |
|---|---|
| Data dodania do BaDAP | 2022-07-29 |
| DOI | 10.1002/rsa.21058 |
| Rok publikacji | 2022 |
| Typ publikacji | artykuł w czasopiśmie |
| Otwarty dostęp |  |
| Czasopismo/seria | Random Structures & Algorithms |
Abstract
The irregularity strength of a simple graph G = (V, E), denoted s(G) is a certain measure of the level of irregularity of a graph. It indicates how hard it is to make an irregular multigraph of G via multiplication of its selected edges. It is however more commonly set forth through k- weightings, that is, mappings. omega : E -> {1, 2,., k}, assigning every vertex v. V the weighted degree sigma (v) := Kappa e is an element of v omega(e). In this setting, s(G) is precisely defined as the least k admitting a k- weighting of G which attributes pairwise distinct weighted degrees to all vertices of G. It is known that s(G) > n/d in the case of d- regular graphs with order n and d > 1. An open conjecture of Faudree and Lehel from the 1980s states that s(G) <= n/d + c in turn for some finite constant c independent of d. It is believed that the natural strengthening of this conjecture toward all graphs where d is substituted by the minimum degree.. should also hold. We confirm this supposition in the case of random graphs. Namely, we showthat asymptotically almost surely the generalization of Faudree-Lehel Conjecture holds for a random graph G is an element of(n, p) for any constant p, that is, that s(G) takes one of the three values:.n/left perpendicularn/delta right perpendicular+ 1, or left perpendicularn/delta right perpendicular+ 2. This is implied by the fact that a.a.s. p- 1 < s(G) =.p-1. + 2, and hence n/delta < s(G) < n/delta + 3.
