In connection with the so-called 1-2-3 Conjecture, we introduce and study a new problem related to proper labellings. In the regular problem, proper labellings of graphs are designed by assigning strictly positive labels to the edges so that any two adjacent vertices get incident to distinct sums of labels, and the main goal, for a given graph, is to minimise the value of the largest label assigned. In the new problem we introduce, we construct proper labellings through pushing vertices, where pushing a vertex means increasing by $1$ the labels assigned to all edges incident to that vertex. We focus on the study of two related metrics of interest, being the total number of times vertices have been pushed, and the maximum number of times a vertex has been pushed, which we aim at minimising, for given graphs. As a contribution, we establish bounds, some of which are tight, on these two parameters, in general and for particular graph classes. We also prove that minimising any of the two parameters is an \textsf{NP}-hard problem. Finally, we also compare our new problem with the original one, and raise directions and questions for further work on the topic.
Discrete Mathematics & Theoretical Computer Science