2019/12/17 by Jakub Przybyło, Przybyło, Jakub
Mathematics · #Combinatorics (math.CO) #FOS: Mathematics #Finite Group Theory Research #Graph theory and applications #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.1912.07858
openalex publication_date 2019/12/17 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The irregularity strength of a graph G, s(G), is the least k admitting\na 1,2,\…,k -weighting of the edges of G assuring distinct weighted\ndegrees of all vertices, or equivalently the least possible maximal edge\nmultiplicity in an irregular multigraph obtained of G via multiplying some of\nits edges. The most well-known open problem concerning this graph invariant is\nthe conjecture posed in 1987 by Faudree and Lehel that there exists a constant\nC such that s(G)\≤ \(n)/(d)+C for each d-regular graph G with n\nvertices and d\≥ 2 (while a straightforward counting argument yields\ns(G)\≥ \(n+d-1)/(d)). The best known results towards this imply that\ns(G)\≤ 6 lceil\(n)/(d) rceil for every d-regular graph G with n\nvertices and d\≥ 2, while s(G)\≤ (4+o(1))\(n)/(d)+4 if d\≥\nn0.5\ln n.\n We show that the conjecture of Faudree and Lehel holds asymptotically in the\ncases when d is neither very small nor very close to n. We in particular\nprove that for large enough n and d\∈ [\ln8n,\(n)/(\ln3 n)],\ns(G)\≤ \(n)/(d)(1+\(8)/(\ln n)), and thereby we show that s(G) =\n\(n)/(d)(1+o(1)) then. We moreover prove the latter to hold already when\nd\∈ [\ln1+\εn,\(n)/(\ln^\ε n)] where \ε\nis an arbitrary positive constant.\n