Szczegóły publikacji
Opis bibliograficzny
On the asymptotic confirmation of the Faudree-Lehel conjecture for general graphs / Jakub PRZYBYŁO, Fan Wei // Combinatorica ; ISSN 0209-9683. — 2023 — vol. 43 iss. 4, s. 791–826. — Bibliogr. s. 825–826, Abstr. — Publikacja dostępna online od: 2023-05-10
Autorzy (2)
- AGHPrzybyło Jakub
- Wei Fan
Słowa kluczowe
Dane bibliometryczne
| ID BaDAP | 148635 |
|---|---|
| Data dodania do BaDAP | 2023-11-13 |
| Tekst źródłowy | URL |
| DOI | 10.1007/s00493-023-00036-5 |
| Rok publikacji | 2023 |
| Typ publikacji | artykuł w czasopiśmie |
| Otwarty dostęp |  |
| Czasopismo/seria | Combinatorica |
Abstract
Given a simple graph G, the irregularity strength of G, denoted by s(G), is the least positive integer k such that there is a weight assignment on edges f: E(G) → { 1 , 2 , ⋯ , k} attributing distinct weighted degrees: f~ (v) : = ∑ u:{u,v}∈E(G)f({ u, v}) to all vertices v∈ V(G) . It is straightforward that s(G) ≥ n/ d for every d-regular graph G on n vertices with d> 1 . In 1987, Faudree and Lehel conjectured in turn that there is an absolute constant c such that s(G) ≤ n/ d+ c for all such graphs. Even though the conjecture has remained open in almost all relevant cases, it is more generally believed that there exists a universal constant c such that s(G) ≤ n/ δ+ c for every graph G on n vertices with minimum degree δ≥ 1 which does not contain an isolated edge; In this paper we confirm that the generalized Faudree–Lehel Conjecture holds for graphs with δ≥ nβ where β is any fixed constant larger than 0.8; Furthermore, we confirm that the conjecture holds in general asymptotically. That is, we prove that for any ε∈ (0 , 0.25) there exist absolute constants c1, c2 such that for all graphs G on n vertices with minimum degree δ≥ 1 and without isolated edges, s(G)≤nδ(1+c1δε)+c2 ; We thereby extend in various aspects and strengthen a recent result of Przybyło, who showed that s(G)≤nd(1+1lnε/19n)=nd(1+o(1)) for d-regular graphs with d∈ [ln 1+εn, n/ ln εn] . We also improve the earlier general upper bound: s(G)<6nδ+6 of Kalkowski, Karoński and Pfender.
