On asymptotic confirmation of the Faudree-Lehel Conjecture on the irregularity strength of graphs

EUROCOMB’23

Jakub Przybyło Fan Wei

https://doi.org/10.5817/CZ.MUNI.EUROCOMB23-106

PDF
Abstract
We call a multigraph irregular if it has pairwise distinct vertex degrees. No nontrivial (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,\ldots,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 invariant is the conjecture posed in 1987 by Faudree and Lehel that there exists an absolute constant $C$ such that $s(G)\leq \frac{n}{d}+C$ for each $d$-regular graph $G$ with $n$ vertices and $d\geq 2$, whereas a straightforward counting argument implies that $s(G)\geq \frac{n}{d}+\frac{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 of irregular subgraphs, introduced recently by Alon and Wei, and progress in research concerning these.

Pages:
766–773
References

L. Addario-Berry, K. Dalal, C. McDiarmid, B.A. Reed, A. Thomason, Vertex- Colouring Edge-Weightings, Combinatorica 27(1) (2007) 1-12.
https://doi.org/10.1007/s00493-007-0041-6

L. Addario-Berry, K. Dalal, B.A. Reed, Degree Constrained Subgraphs, Discrete Appl. Math. 156(7) (2008) 1168-1174.
https://doi.org/10.1016/j.dam.2007.05.059

M. Aigner, E. Triesch, Irregular assignments of trees and forests, SIAM J. Discrete Math. 3(4) (1990) 439-449.
https://doi.org/10.1137/0403038

N. Alon, F. Wei, Irregular subgraphs, Combinatorics, Probability and Computing 32(2) (2023) 269-283. doi:10.1017/S0963548322000220
https://doi.org/10.1017/S0963548322000220

D. Amar, Irregularity strength of regular graphs of large degree, Discrete Math. 114 (1993) 9-17.
https://doi.org/10.1016/0012-365X(93)90351-S

T. Bartnicki, J. Grytczuk, S. Niwczyk, Weight Choosability of Graphs, J. Graph Theory 60(3) (2009) 242-256.
https://doi.org/10.1002/jgt.20354

J. Bensmail, A 1-2-3-4 result for the 1-2-3 Conjecture in 5-regular graphs, Discrete Appl. Math. 257 (2019) 31-39.
https://doi.org/10.1016/j.dam.2018.10.008

T. Bohman, D. Kravitz, On the irregularity strength of trees, J. Graph Theory 45 (2004) 241-254.
https://doi.org/10.1002/jgt.10158

L. Cao, Total weight choosability of graphs: Towards the 1-2-3-conjecture, J. Combin. Theory Ser. B 149(1-2) 109-146
https://doi.org/10.1016/j.jctb.2021.01.008

G. Chartrand, P. Erdős, O.R. Oellermann, How to Define an Irregular Graph, College Math. J. 19(1) (1988) 36-42.
https://doi.org/10.1080/07468342.1988.11973088

G. Chartrand, M.S. Jacobson, J. Lehel, O.R. Oellermann, S. Ruiz, F. Saba, Irregular networks, Congr. Numer. 64 (1988) 197-210.

B. Cuckler, F. Lazebnik, Irregularity Strength of Dense Graphs, J. Graph Theory 58(4) (2008) 299-313.
https://doi.org/10.1002/jgt.20313

J.H. Dinitz, D.K. Garnick, A. Gyárfás, On the irregularity strength of the m × n grid, J. Graph Theory 16 (1992) 355-374.
https://doi.org/10.1002/jgt.3190160409

A. Dudek, D. Wajc, On the complexity of vertex-coloring edge-weightings, Discrete Math. Theor. Comput. Sci. 13(3) (2011) 45-50.
https://doi.org/10.46298/dmtcs.548

G. Ebert, J. Hemmeter, F. Lazebnik, A.J. Woldar, On the irregularity strength of some graphs, Congr. Numer. 71 (1990) 39-52.

R.J. Faudree, M.S. Jacobson, J. Lehel, R. Schelp, Irregular networks, regular graphs and integer matrices with distinct row and column sums, Discrete Math. 76 (1989) 223-240.
https://doi.org/10.1016/0012-365X(89)90321-X

R.J. Faudree, J. Lehel, Bound on the irregularity strength of regular graphs, Colloq Math Soc Jańos Bolyai, 52, Combinatorics, Eger North Holland, Amsterdam, (1987), 247-256.

M. Ferrara, R.J. Gould, M. Karoński, F. Pfender, An iterative approach to graph irregularity strength, Discrete Appl. Math. 158 (2010) 1189-1194.
https://doi.org/10.1016/j.dam.2010.02.003

J. Fox, S. Luo, H.T. Pham, On random irregular subgraphs, arXiv:2207.13651.

A. Frieze, R.J. Gould, M. Karoński, F. Pfender, On Graph Irregularity Strength, J. Graph Theory 41(2) (2002) 120-137.
https://doi.org/10.1002/jgt.10056

J.A. Gallian, Graph Labeling, Electron. J. Combin. (2019) 1-535, Dynamic survey DS6.

A. Gyárfás, The irregularity strength of Km,m is 4 for odd m, Discrete Math. 71 (1998) 273-274.
https://doi.org/10.1016/0012-365X(88)90106-9

M. Kalkowski, A note on 1,2-Conjecture, in Ph.D. Thesis, Poznań, 2009.

M. Kalkowski, M. Karoński, F. Pfender, A new upper bound for the irregularity strength of graphs, SIAM J. Discrete Math. 25 (2011) 1319-1321.
https://doi.org/10.1137/090774112

M. Kalkowski, M. Karoński, F. Pfender, Vertex-coloring edge-weightings: Towards the 1-2-3 conjecture, J. Combin. Theory Ser. B 100 (2010) 347-349.
https://doi.org/10.1016/j.jctb.2009.06.002

M. Karoński, T. Łuczak, A. Thomason, Edge weights and vertex colours, J. Combin. Theory Ser. B 91 (2004) 151-157.
https://doi.org/10.1016/j.jctb.2003.12.001

R. Keusch, A Solution to the 1-2-3 Conjecture, arXiv:2303.02611.

R. Keusch, Vertex-coloring graphs with 4-edge-weightings, Combinatorica, to appear.

J. Lehel, Facts and quests on degree irregular assignments, Graph Theory, Combinatorics and Applications, Willey, New York, 1991, 765-782.

P. Majerski, J. Przybyło, On the irregularity strength of dense graphs, SIAM J. Discrete Math. 28(1) (2014) 197-205.
https://doi.org/10.1137/120886650

T. Nierhoff, A tight bound on the irregularity strength of graphs, SIAM J. Discrete Math. 13(3) (2000) 313-323.
https://doi.org/10.1137/S0895480196314291

J. Przybyło, A generalization of Faudree-Lehel Conjecture holds almost surely for random graphs, Random Struct Alg. 61 (2022) 383-396.
https://doi.org/10.1002/rsa.21058

J. Przybyło, Asymptotic confirmation of the Faudree-Lehel Conjecture on irregularity strength for all but extreme degrees, J. Graph Theory 100 (2022) 189-204.
https://doi.org/10.1002/jgt.22772

J. Przybyło, Irregularity strength of regular graphs, Electron. J. Combin. 15(1) (2008) ♯R82.
https://doi.org/10.37236/806

J. Przybyło, Linear bound on the irregularity strength and the total vertex irregularity strength of graphs, SIAM J. Discrete Math. 23(1) (2009) 511-516.
https://doi.org/10.1137/070707385

J. Przybyło, The 1-2-3 Conjecture almost holds for regular graphs, J. Combin. Theory Ser. B 147 (2021) 183-200.
https://doi.org/10.1016/j.jctb.2020.03.005

J. Przybyło, The 1-2-3 Conjecture holds for graphs with large enough minimum degree, Combinatorica 42 (2022) 1487-1512.
https://doi.org/10.1007/s00493-021-4822-0

J. Przybyło, F. Wei, On the asymptotic confirmation of the Faudree-Lehel Conjecture for general graphs, Combinatorica (2023), https://doi.org/10.1007/s00493-023-00036- 5.
https://doi.org/10.1007/s00493-023-00036-5

J. Przybyło, F. Wei, Short proof of the asymptotic confirmation of the Faudree-Lehel Conjecture, arXiv:2109.13095.

C. Thomassen, Y. Wu, C.Q. Zhang, The 3-flow conjecture, factors modulo k, and the 1-2-3 conjecture, J. Combin. Theory Ser. B 121 (2016) 308-325.
https://doi.org/10.1016/j.jctb.2016.06.010

T. Wang, Q. Yu, On vertex-coloring 13-edge-weighting, Front. Math. China 3(4) (2008) 581-587.
https://doi.org/10.1007/s11464-008-0041-x

T. Wong, X. Zhu, Every graph is (2,3)-choosable, Combinatorica 36(1) (2016) 121-127.
https://doi.org/10.1007/s00493-014-3057-8

L. Zhong, The 1-2-3-conjecture holds for dense graphs, J. Graph Theory 90 (2019) 561-564.
https://doi.org/10.1002/jgt.22413

X. Zhu, Every nice graph is (1,5)-choosable, J. Combin. Theory Ser. B 157 (2022) 524-551.
https://doi.org/10.1016/j.jctb.2022.08.006

Metrics

0

Views

0

PDF views

Creative Commons License

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

Copyright © 2023 Jakub Przybyło, Fan Wei

PDF