Szczegóły publikacji
Opis bibliograficzny
On asymptotic confirmation of the Faudree-Lehel Conjecture on the irregularity strength of graphs / Jakub PRZYBYŁO, Fan Wei // W: EUROCOMB'23 [Dokument elektroniczny] : European conference on Combinatorics, Graph Theory and Applications : Prague, Czech Republic, August 28–September 1, 2023. — Wersja do Windows. — Dane tekstowe. — [Prague] : European Conference on Combinatorics, Graph Theory and Applications, [2023]. — (European Conference on Combinatorics, Graph Theory and Applications ; ISSN 2788-3116). — S. 766–773. — Wymagania systemowe: Adobe Reader. — Tryb dostępu: https://journals.muni.cz/eurocomb/article/view/35640/31554 [2024-01-22]. — Bibliogr. s. 770–773, Abstr.
Autorzy (2)
- AGHPrzybyło Jakub
- Wei Fan
Dane bibliometryczne
| ID BaDAP | 151585 |
|---|---|
| Data dodania do BaDAP | 2024-01-31 |
| DOI | 10.5817/CZ.MUNI.EUROCOMB23-106 |
| Rok publikacji | 2023 |
| Typ publikacji | materiały konferencyjne (aut.) |
| Otwarty dostęp |  |
| Creative Commons | |
| Konferencja | EuroConference on Combinatorics, Graph Theory and Applications 2023 |
| Czasopismo/seria | European Conference on Combinatorics, Graph Theory and Applications |
Abstract
We call a multigraph irregular if it has pairwise distinct vertex degrees. No non-trivial (simple) graph is thus irregular. The irregularity strength of a graph G, s(G), is a specific measure of the “level of irregularity” of G. It might be defined as the least k such that one may obtain an irregular multigraph of G by multiplying any selected edges of G, each into at most k its copies. In other words, s(G) is the least k admitting a {1,2, . . . , k}-weighting of the edges of G assuring distinct weighted degrees for all the vertices, where the weighted degree of a vertex is the sum of its incident weights. The most well-known open problem concerning this graph invariantis the conjecture posed in 1987 by Faudree and Lehel that there exists an absolute constant C such that s(G)≤n/d+C for each d-regular graph G with n vertices and d≥2, whereas a straightforward counting argument implies that s(G)≥n/d+(d−1)/d. Until very recently this conjecture had remained widely open. We shall discuss recent results confirming it asymptotically, up to a lower order term. If time permits we shall also mention a few related problems, such as the 1–2–3 Conjecture or the concept ofirregular subgraphs, introduced recently by Alon and Wei, and progress in research concerning these.
