DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

https://doi.org/10.7151/dmgt

Discussiones Mathematicae Graph Theory

Journal Impact Factor (JIF 2023): 0.5

5-year Journal Impact Factor (2023): 0.6

CiteScore (2023): 2.2

SNIP (2023): 0.681

Discussiones Mathematicae Graph Theory

Article in volume

Authors:

J. Bensmail

Julien Bensmail

Université Côte d'Azur

email: julien.bensmail.phd@gmail.com

0000-0002-9292-394X

Title:

Maximising 1’s through proper labellings

PDF

Source:

Discussiones Mathematicae Graph Theory 45(1) (2025) 351-376

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:

  1. 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
  2. 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
  3. 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
  4. 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
  5. 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
  6. G.J. Chang, C. Lu, J. Wu and Q. Yu, Vertex-coloring edge-weightings of graphs, Taiwanese J. Math. 15 (2011) 1807–1813.
  7. G. Chartrand, M.S. Jacobson, J. Lehel, O.R. Oellermann, S. Ruiz and F. Saba, Irregular networks, Congr. Numer. 64 (1988) 197–210.
  8. 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.
  9. M. Karoński, T. Ł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
  10. R. Keusch, A solution to the $1$-$2$-$3$ Conjecture (2023).
    arXiv: 2303.02611
  11. B. Seamone, The $1$-$2$-$3$ Conjecture and related problems: a survey (2012).
    arXiv: 1211.5122
Close