Szczegóły publikacji
Opis bibliograficzny
Asymptotic confirmation of the Faudree–Lehel conjecture on irregularity strength for all but extreme degrees / Jakub PRZYBYŁO // Journal of Graph Theory ; ISSN 0364-9024. — 2022 — vol. 100 iss. 1, s. 189–204. — Bibliogr. s. 203–204, Abstr. — Publikacja dostępna online od: 2021-11-19
Autor
Słowa kluczowe
Dane bibliometryczne
| ID BaDAP | 139768 |
|---|---|
| Data dodania do BaDAP | 2022-04-27 |
| Tekst źródłowy | URL |
| DOI | 10.1002/jgt.22772 |
| Rok publikacji | 2022 |
| Typ publikacji | artykuł w czasopiśmie |
| Otwarty dostęp |  |
| Czasopismo/seria | Journal of Graph Theory |
Abstract
The irregularity strength of a graph (Formula presented.), (Formula presented.), is the least (Formula presented.) admitting a (Formula presented.) -weighting of the edges of (Formula presented.) assuring distinct weighted degrees of all vertices, or equivalently the least possible maximal edge multiplicity in an irregular multigraph obtained of (Formula presented.) via multiplying some of its edges. The most well-known open problem concerning this graph invariant is the conjecture posed in 1987 by Faudree and Lehel that there exists a constant (Formula presented.) such that (Formula presented.) for each (Formula presented.) -regular graph (Formula presented.) with (Formula presented.) vertices and (Formula presented.) (while a straightforward counting argument yields (Formula presented.)). The best known results towards this imply that (Formula presented.) for every (Formula presented.) -regular graph (Formula presented.) with (Formula presented.) vertices and (Formula presented.), while (Formula presented.) if (Formula presented.). We show that the conjecture of Faudree and Lehel holds asymptotically in the cases when (Formula presented.) is neither very small nor very close to (Formula presented.). We in particular prove that for large enough (Formula presented.) and (Formula presented.), (Formula presented.), and thereby we show that (Formula presented.) then. We moreover prove the latter to hold already when (Formula presented.), where (Formula presented.) is an arbitrary positive constant.
