Article in press
Authors:
Title:
Maximising 1’s through proper labellings
PDFSource:
Discussiones Mathematicae Graph Theory
Received: 2023-06-05 , Revised: 2023-12-15 , Accepted: 2023-12-15 , Available online: 2024-01-31 , https://doi.org/10.7151/dmgt.2536
Abstract:
We investigate graph proper labellings, i.e., assignments of labels to
the edges so that no two adjacent vertices are incident to the same sum of
labels, with the additional requirement that label $1$ must be assigned to as
many edges as possible. The study of such objects is motivated by practical
concerns, and by connections with other types of proper labellings in which
other additional properties (such as minimising the sum of assigned labels, or
minimising the use of label $3$) must be met. We prove that maximising $1$'s is
a problem on its own, in that it is not equivalent to any of these other
labelling problems with optimisation concerns. We then provide labelling tools
and techniques for designing proper labellings with many $1$'s. As a result, we
prove that, for several graph classes, it is always possible to design proper
labellings where label $1$ is assigned to about half the edges.
Keywords:
proper labelling, incident sum, label $1$, 1-2-3 conjecture
References:
- O. Baudon, M. Pilśniak, J. Przybyło, M. Senhaji, É. Sopena and M. Woźniak, Equitable neighbour-sum-distinguishing edge and total colourings, Discrete Appl. Math. 222 (2017) 40–53.
https://doi.org/10.1016/j.dam.2017.01.031 - J. Bensmail, F. Fioravantes and F. Mc Inerney, On the role of $3$s for the $1$-$2$-$3$ Conjecture, Theoret. Comput. Sci. 892 (2021) 238–257.
https://doi.org/10.1016/j.tcs.2021.09.023 - J. Bensmail, F. Fioravantes, F. Mc Inerney and N. Nisse, Further results on an equitable $1$-$2$-$3$ Conjecture, Discrete Appl. Math. 297 (2021) 1–20.
https://doi.org/10.1016/j.dam.2021.02.037 - J. Bensmail, F. Fioravantes and N. Nisse, On proper labellings of graphs with minimum label sum, Algorithmica 84 (2022) 1030–1063.
https://doi.org/10.1007/s00453-021-00903-x - J. Bensmail, M. Senhaji and K. Szabo Lyngsie, On a combination of the $1$-$2$-$3$ Conjecture and the Antimagic Labelling Conjecture, Discrete Math. Theor. Comput. Sci. 19(1) (2017) #21.
https://doi.org/10.23638/DMTCS-19-1-21 - G.J. Chang, C. Lu, J. Wu and Q. Yu, Vertex-coloring edge-weightings of graphs, Taiwanese J. Math. 15 (2011) 1807–1813.
- G. Chartrand, M.S. Jacobson, J. Lehel, O.R. Oellermann, S. Ruiz and F. Saba, Irregular networks, Congr. Numer. 64 (1988) 197–210.
- F. Fioravantes, N. Melissinos and T. Triomatis, Complexity of finding maximum locally irregular induced subgraphs, in: Proc. 18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022), A. Czumaj and Q. Xin (Ed(s)), (Dagstuhl Publishing, Germany 2022) #24.
- M. Karoński, T. \L uczak and 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 (2023).
arXiv: 2303.02611 - B. Seamone, The $1$-$2$-$3$ Conjecture and related problems: a survey (2012).
arXiv: 1211.5122
Close