Bounding the distant irregularity strength of graphs via a non-uniformly biased random weight assignment. (English) Zbl 1543.05160
Summary: Given an edge \(k\)-weighting \(\omega :E\to [k]\) of a graph \(G=(V, E)\), the weighted degree of a vertex \(v \in V\) is the sum of its incident weights. The least \(k\) for which there exists an edge \(k\)-weighting such that the resulting weighted degrees of the vertices at distance at most \(r\) in \(G\) are distinct is called the \(r\)-distant irregularity strength, and denoted \(s_r (G)\). This concept links the well-known 1-2-3 Conjecture, corresponding to \(s_1 (G)\), with the irregularity strength of graphs, \(s(G)\), which coincides with \(s_r (G)\) for every \(r\) at least the diameter of \(G\). It is believed that for every \(r\geq 2\), \(s_r (G) \leq (1+o(1)) \varDelta^{r-1}\), where \(\varDelta\) is the maximum degree of \(G\), while it is known that \(s_r (G) \leq 6 \varDelta^{r-1}\) in general and \(s_r (G) \leq (4+o(1)) \varDelta^{r-1}\) for graphs with minimum degree \(\delta\) at least \(\log^8 \varDelta\). We apply the probabilistic method in order to improve these results and show that graphs with \(\delta \gg \ln \varDelta\) satisfy \(s_r (G) \leq (e +o(1)) \varDelta^{r-1}\) as \(\varDelta \to \infty\).
MSC:
| 05C78 | Graph labelling (graceful graphs, bandwidth, etc.) |
| 05C22 | Signed and weighted graphs |
| 05C07 | Vertex degrees |
| 05C12 | Distance in graphs |
| 05D40 | Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) |
References:
| [1] | Chartrand, G.; Jacobson, M. S.; Lehel, J.; Oellermann, O. R.; Ruiz, S.; Saba, F., Irregular networks, Congr. Numer., 64, 197-210, 1988 · Zbl 0671.05060 |
| [2] | Chartrand, G.; Erdős, P.; Oellermann, O. R., How to define an irregular graph, College Math. J., 19, 1, 36-42, 1988 · Zbl 0995.05516 |
| [3] | Aigner, M.; Triesch, E., Irregular assignments of trees and forests, SIAM J. Discrete Math., 3, 4, 439-449, 1990 · Zbl 0735.05049 |
| [4] | Nierhoff, T., A tight bound on the irregularity strength of graphs, SIAM J. Discrete Math., 13, 3, 313-323, 2000 · Zbl 0947.05067 |
| [5] | Faudree, R. J.; Lehel, J., Bound on the irregularity strength of regular graphs, (Colloq Math Soc Jańos Bolyai, Vol. 52, 1987, Combinatorics, Eger North Holland: Combinatorics, Eger North Holland Amsterdam), 247-256 · Zbl 0697.05048 |
| [6] | Lehel, J., Facts and quests on degree irregular assignments, (Graph Theory, Combinatorics and Applications, 1991, Willey: Willey New York), 765-782 · Zbl 0841.05052 |
| [7] | Cuckler, B.; Lazebnik, F., Irregularity strength of dense graphs, J. Graph Theory, 58, 4, 299-313, 2008 · Zbl 1188.05112 |
| [8] | Przybyło, J.; Wei, F., On the asymptotic confirmation of the Faudree-Lehel Conjecture for general graphs, Combinatorica, 43, 791-826, 2023 · Zbl 07745901 |
| [9] | Przybyło, J.; Wei, F., Short proof of the asymptotic confirmation of the Faudree-Lehel Conjecture, Electron. J. Combin., 30, 4, #P4.27, 2023 · Zbl 1532.05079 |
| [10] | Faudree, R. J.; Jacobson, M. S.; Lehel, J.; Schelp, R., Irregular networks, regular graphs and integer matrices with distinct row and column sums, Discrete Math., 76, 223-240, 1989 · Zbl 0685.05029 |
| [11] | Frieze, A.; Gould, R. J.; Karoński, M.; Pfender, F., On graph irregularity strength, J. Graph Theory, 41, 2, 120-137, 2002 · Zbl 1016.05045 |
| [12] | Kalkowski, M.; Karoński, M.; Pfender, F., A new upper bound for the irregularity strength of graphs, SIAM J. Discrete Math., 25, 1319-1321, 2011 · Zbl 1237.05183 |
| [13] | Przybyło, J., Asymptotic confirmation of the faudree-lehel conjecture on irregularity strength for all but extreme degrees, J. Graph Theory, 100, 189-204, 2022 · Zbl 1522.05406 |
| [14] | Przybyło, J., Irregularity strength of regular graphs, Electron. J. Combin., 15, 1, #R82, 2008 · Zbl 1163.05329 |
| [15] | Przybyło, J., Linear bound on the irregularity strength and the total vertex irregularity strength of graphs, SIAM J. Discrete Math., 23, 1, 511-516, 2009 · Zbl 1216.05135 |
| [16] | Amar, D., Irregularity strength of regular graphs of large degree, Discrete Math., 114, 9-17, 1993 · Zbl 0796.05048 |
| [17] | Majerski, P.; Przybyło, J., On the irregularity strength of dense graphs, SIAM J. Discrete Math., 28, 1, 197-205, 2014 · Zbl 1293.05341 |
| [18] | Przybyło, J., A generalization of Faudree-Lehel Conjecture holds almost surely for random graphs, Random Struct. Algorithms, 61, 383-396, 2022 · Zbl 1522.05444 |
| [19] | Bohman, T.; Kravitz, D., On the irregularity strength of trees, J. Graph Theory, 45, 241-254, 2004 · Zbl 1034.05015 |
| [20] | Dinitz, J. H.; Garnick, D. K.; Gyárfás, A., On the irregularity strength of the \(m \times n\) grid, J. Graph Theory, 16, 355-374, 1992 · Zbl 0771.05055 |
| [21] | Ferrara, M.; Gould, R. J.; Karoński, M.; Pfender, F., An iterative approach to graph irregularity strength, Discrete Appl. Math., 158, 1189-1194, 2010 · Zbl 1213.05119 |
| [22] | Ebert, G.; Hemmeter, J.; Lazebnik, F.; Woldar, A. J., On the irregularity strength of some graphs, Congr. Numer., 71, 39-52, 1990 · Zbl 0696.05050 |
| [23] | Gyárfás, A., The irregularity strength of \(K_{m , m}\) is \(4\) for odd \(m\), Discrete Math., 71, 273-274, 1998 · Zbl 0681.05066 |
| [24] | Gallian, J. A., Graph labeling, Electron. J. Combin., 1-535, 2019, Dynamic survey DS6 |
| [25] | B. Seamone, The 1-2-3 Conjecture and related problems: a survey, Technical report, 2012, available online at http://arxiv.org/abs/1211.5122. |
| [26] | Karoński, M.; Łuczak, T.; Thomason, A., Edge weights and vertex colours, J. Combin. Theory Ser. B, 91, 151-157, 2004 · Zbl 1042.05045 |
| [27] | Addario-Berry, L.; Dalal, K.; McDiarmid, C.; Reed, B. A.; Thomason, A., Vertex-colouring edge-weightings, Combinatorica, 27, 1, 1-12, 2007 · Zbl 1127.05034 |
| [28] | Addario-Berry, L.; Dalal, K.; Reed, B. A., Degree constrained subgraphs, Discrete Appl. Math., 156, 7, 1168-1174, 2008 · Zbl 1147.05055 |
| [29] | Kalkowski, M.; Karoński, M.; Pfender, F., Vertex-coloring edge-weightings: Towards the 1-2-3 conjecture, J. Combin. Theory Ser. B, 100, 347-349, 2010 · Zbl 1209.05087 |
| [30] | Keusch, R., A solution to the 1-2-3 conjecture, J. Combin. Theory Ser. B, 166, 183-202, 2024 · Zbl 1533.05235 |
| [31] | Keusch, R., Vertex-coloring graphs with 4-edge-weightings, Combinatorica, 43, 3, 651-658, 2023 · Zbl 1538.05098 |
| [32] | Przybyło, J., The 1-2-3 conjecture almost holds for regular graphs, J. Combin. Theory Ser. B, 147, 183-200, 2021 · Zbl 1458.05099 |
| [33] | Przybyło, J., The 1-2-3 conjecture holds for graphs with large enough minimum degree, Combinatorica, 42, 1487-1512, 2022 |
| [34] | Wang, T.; Yu, Q., On vertex-coloring 13-edge-weighting, Front. Math. China, 3, 4, 581-587, 2008 · Zbl 1191.05048 |
| [35] | Bensmail, J., A 1-2-3-4 result for the 1-2-3 conjecture in 5-regular graphs, Discrete Appl. Math., 257, 31-39, 2019 · Zbl 1406.05042 |
| [36] | Dudek, A.; Wajc, D., On the complexity of vertex-coloring edge-weightings, Discrete Math. Theor. Comput. Sci., 13, 3, 45-50, 2011 · Zbl 1283.05093 |
| [37] | Thomassen, C.; Wu, Y.; Zhang, C. Q., The \(3\)-flow conjecture, factors modulo \(k\), and the \(1-2-3\) conjecture, J. Combin. Theory Ser. B, 121, 308-325, 2016 · Zbl 1348.05085 |
| [38] | Zhong, L., The 1-2-3-conjecture holds for dense graphs, J. Graph Theory, 90, 561-564, 2019 · Zbl 1416.05163 |
| [39] | Bartnicki, T.; Grytczuk, J.; Niwczyk, S., Weight choosability of graphs, J. Graph Theory, 60, 3, 242-256, 2009 · Zbl 1210.05138 |
| [40] | L. Cao, Total weight choosability of graphs: Towards the 1-2-3-conjecture, J. Combin. Theory Ser. B 149 (1-2) 109-146. · Zbl 1468.05103 |
| [41] | Wong, T.; Zhu, X., Every graph is (2, 3)-choosable, Combinatorica, 36, 1, 121-127, 2016 · Zbl 1374.05106 |
| [42] | Zhu, X., Every nice graph is (1, 5)-choosable, J. Combin. Theory Ser. B, 157, 524-551, 2022 · Zbl 1497.05104 |
| [43] | Przybyło, J., Distant irregularity strength of graphs, Discrete Math., 313, 2875-2880, 2013 · Zbl 1281.05058 |
| [44] | Przybyło, J., Distant irregularity strength of graphs with bounded minimum degree, Discrete Appl. Math., 233, 159-165, 2017 · Zbl 1372.05043 |
| [45] | Alon, N.; Spencer, J. H., (The Probabilistic Method, 2000, Wiley: Wiley New York) · Zbl 0996.05001 |
| [46] | Janson, S.; Łuczak, T.; Ruciński, A., Random Graphs, 2000, Wiley: Wiley New York · Zbl 0968.05003 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
