Julien Bensmail

Maximising 1's through Proper Labellings

Keywords: proper labelling, incident sum, label 1, 1-2-3 Conjecture

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.

Introduction

We deal with a variant of proper labellings of graphs, which are usually defined as follows. Let G be a graph. A k-labelling ℓ of G is an assignment ℓ ∶ E(G) → {1, . . . , k} of labels (from {1, . . . , k}) to the edges of G. For every vertex v of G, one can then compute the sum σ(v) of labels incident to v by ℓ, being formally defined as σ(v) = ∑ u∈N (v) ℓ(vu). If no two adjacent vertices of G have the same sum by ℓ, or, in other words, if σ(u) ≠ σ(v) for every edge uv ∈ E(G), then we say ℓ is proper. We denote by χ Σ (G) the smallest k ≥ 1, if any, such that G admits proper k-labellings. Actually, greedy labelling arguments can be invoked to prove formally that χ Σ (G) is well defined if and only if G is nice, i.e., does not contain K 2 (the complete graph on two vertices) as a connected component.

Proper labellings have been intensively studied in the context of the so-called 1-2-3 Conjecture (stating that χ Σ (G) ≤ 3 holds for every nice graph G) raised by Karoński, Łuczak, and Thomason [START_REF] Karoński | Edge weights and vertex colours[END_REF] in 2004, whose resolution was recently claimed by Keusch [START_REF] Keusch | A Solution to the 1-2-3 Conjecture[END_REF]. We refer the interested reader to e.g. [START_REF] Bensmail | On the Role of 3s for the 1-2-3 Conjecture[END_REF][START_REF] Bensmail | On Proper Labellings of Graphs with Minimum Label Sum[END_REF][START_REF] Seamone | The 1-2-3 Conjecture and related problems: a survey[END_REF] for an overview of the investigations dedicated to proper labellings (and their variants) to date.

The origins behind these notions trace back to the 1980s, to considerations first raised by Chartrand et al. [START_REF] Chartrand | Irregular networks[END_REF]. In the kind of problems they introduced there, a graph G is given, and the goal is to make it somewhat irregular, i.e., so that some of its vertices have pairwise different degrees, by replacing its edges with parallel edges, all the while keeping the resulting multigraph of relatively small size (in terms of number of edges). Such a problem can be formalised and studied through the lens of labellings satisfying certain distinction properties. As an illustration, consider proper labellings. Let G be a nice graph, given together with a proper k-labelling ℓ (for any k ≥ 1). Let M (G, ℓ) be the multigraph obtained from G by considering every edge e = uv of G in turn, and replacing e with ℓ(e) ≥ 1 parallel edges1 (i.e., all joining u and v). Since ℓ is proper, note that M (G, ℓ) must be locally irregular, meaning that no two of its adjacent vertices have the same degree. Also, by the way M (G, ℓ) was constructed, G and M (G, ℓ) have the same structure, as no new adjacencies have been created. Now, in this formalism, the parameter χ Σ (G) means there is a way to obtain such a locally irregular M (G, ℓ) from G by replacing every edge by at most χ Σ (G) parallel edges. The 1-2-3 Conjecture, now, implies there is always a locally irregular M (G, ℓ) with size at most 3|E(G)|. This was one of the main motivations from [START_REF] Chartrand | Irregular networks[END_REF] for investigating labellings minimising the maximum value of an assigned label.

As raised in [START_REF] Bensmail | On Proper Labellings of Graphs with Minimum Label Sum[END_REF], at least in the context of proper labellings, minimising the maximum label value by ℓ is not a guarantee that M (G, ℓ) will necessarily be the smallest locally irregular multigraph overlying G. This led the authors to consider proper labellings minimising the sum of assigned labels, which we will introduce more formally in later Section 2. One intuitive way of minimising the label sum by a proper 3-labelling is through minimising the number of assigned 3's, which is a concern considered by other authors [START_REF] Bensmail | On the Role of 3s for the 1-2-3 Conjecture[END_REF].

In this work, we introduce and study the sort of dual approach, consisting in maximising 1's by proper labellings. Our formal terminology is as follows. For a nice graph G, a labelling ℓ, and an x ∈ N * , we denote by nb(ℓ, x) the number of edges of G that are assigned label x by ℓ. For any k ≥ χ Σ (G), we denote by maxOne(G, k) the maximum value of nb(ℓ, 1) over all proper k-labellings ℓ of G. Last, we denote by maxOne(G) the maximum value of maxOne(G, k) for some k ≥ 1. Note that we always have 0 ≤ maxOne(G) ≤ |E(G)|, where the upper bound is attained if and only if G is locally irregular. Also, as we will prove later through Theorem 3.1, there is no k ≥ 1 such that maxOne(G) = maxOne(G, k) for every nice graph G, which justifies to wonder about the more general parameter maxOne(G) (and not just about maxOne(G, 3), which could make sense due to the 1-2-3 Conjecture). From the motivation point of view and the connection between graphs G and associated overlying locally irregular multigraphs M (G, ℓ), considering proper labellings ℓ assigning many 1's also justifies in that the corresponding locally irregular multigraph M (G, ℓ) has many edges with multiplicity 1, and, thus, is even closer to the original graph G.

We organise this work as follows. In Section 2, we start by making more formal some of the connections we mentioned earlier, between proper labellings maximising 1's and other types of proper labellings fulfilling additional requirements. In Section 3, we investigate first properties of the parameter maxOne, showing, for instance, that it sometimes requires to assign arbitrarily large labels, and that determining this parameter is quite different from determining other related parameters (such as the minimum label sum by a proper labelling). We also raise, in that section, our leading conjecture, Conjecture 3.6, stating, roughly, that, at worst, we should always be able to design a proper labelling assigning label 1 to about half of the edges, for any nice graph. We then prove this conjecture for several graph classes through Sections 4 and 5, along which the proofs and arguments we employ are of increasing complexity. In particular, in Section 5, we get to exploring both known and new labelling techniques and tools to establish lower bounds on the parameter maxOne. We conclude with perspectives for further work on the topic in Section 6.

Related parameters and their interplay

In this section, we recall some other optimisation problems involving proper labellings from previous works. In particular, we make explicit their connections with the problem of maximising 1's, from which we can establish first properties of the parameter maxOne.

Proper labellings with minimum number of 3's

In [START_REF] Bensmail | On the Role of 3s for the 1-2-3 Conjecture[END_REF], the authors considered notions that are, to some extent, dual to those we introduce in the current work. Namely, they considered the existence of graphs requiring "lots" of 3's in all of their proper 3-labellings (which the 1-2-3 Conjecture is precisely about). Formally, this leads to the parameter minThree(G), which, for a given nice graph G, is defined as the smallest x such that, for all proper 3-labellings ℓ of G, we have nb(ℓ, 3) ≤ x.

While the parameters maxOne(G) and minThree(G) might seem dual ones at first glance, a fundamental difference lies in the fact that, for the latter parameter, we are focusing on proper 3-labellings only (while, for the former parameter, we are considering proper labellings assigning labels that can be arbitrarily large). One of the reasons why the latter parameter is defined this way is because, when assigning arbitrarily large labels, we can always make sure to avoid assigning label 3 (and, more generally, any given label):

Proposition 2.1. Every nice graph admits proper labellings ℓ with nb(ℓ, 3) = 0.

Proof. Assume ℓ is a proper labelling of a graph G such that nb(ℓ, 3) > 0. Let uv be an edge of G with ℓ(uv) = 3. Note that changing the label assigned to uv cannot result in u and v being in conflict2 (as ℓ(uv) contributes to both σ(u) and σ(v)). In other words, when changing the label assigned to uv, to preserve properness we only need to make sure that u does not get in conflict with its at most ∆(G)-1 neighbours other than v, and similarly that v does not get in conflict with its at most ∆(G) -1 neighbours other than u. Thus, there must be a label in {1, . . . , 2∆(G)} ∖ {3} that can be assigned to uv without introducing conflicts. Then we end up with a proper labelling ℓ ′ of G with nb(ℓ ′ , 3) = nb(ℓ, 3) -1, and by repeating these arguments while G has edges assigned label 3, eventually we get to a situation where G is labelled in a proper way and no edges are assigned label 3.

Due to these facts, the real parameter dual (in spirit) to minThree(G) is actually maxOne(G, 3), from which we deduce that the following relationship holds:

Observation 2.2. If G is a nice graph, then maxOne(G, 3) ≤ |E(G)| -minThree(G).
Indeed, by definition, every proper 3-labelling ℓ of a nice graph G must assign label 3 to at least minThree(G) edges of G. This implies at most |E(G)| -minThree(G) edges of G can be assigned label 1 or 2 by ℓ, which yields the claimed inequality.

As will be proved in later Theorem 3.1, there are nice graphs G for which the smallest k ≥ 1 for which maxOne(G) = maxOne(G, k) is arbitrarily large, and thus we can have k > 3. Hence, apart from consequences on the very particular case maxOne(G, 3), we do not get much on maxOne(G) from results from [START_REF] Bensmail | On the Role of 3s for the 1-2-3 Conjecture[END_REF]. We will actually prove in Theorem 3.4 that maximising 1's and minimising 3's by proper 3-labellings are distant problems.

So that the reader can compare the results from the current work and those from [START_REF] Bensmail | On the Role of 3s for the 1-2-3 Conjecture[END_REF], we now give a brief summary of the main contributions of that work. First, the authors proved that there is no absolute constant x ≥ 1 such that every nice connected graph admits a proper 3-labelling assigning label 3 to at most x edges. This led them to investigating classes of connected graphs requiring a large fraction of their edges be assigned label 3 by any proper 3-labelling. They then exhibited constructions of arbitrarily large connected graphs in which label 3 must be assigned to at least a tenth of the edges, and also provided other constructions, where the edge fraction is sometimes a bit smaller, providing graphs with specific properties (degree constraints, structural properties, etc.). These constructions and other arguments led the authors to conjecture that, perhaps, all nice connected graphs admit proper 3-labellings assigning label 3 to at most about a third of the edges, a conjecture they verified for several classes of nice connected graphs (dense enough graphs, graphs with large girth, cubic graphs, cacti, Halin graphs, etc.). Last, they also established general properties of the parameter minThree; in particular, for any given nice connected graph G and fixed x ≥ 1, it is NP-complete to decide whether minThree(G) ≤ x.

Equitable proper labellings

The reason why maximising 1's and minimising 3's by proper 3-labellings might sound as dual problems, is because labels 1 and 3 seem sort of interchangeable. This is actually true in some contexts, such as in regular graphs, as noticed e.g. in [START_REF] Bensmail | On the Role of 3s for the 1-2-3 Conjecture[END_REF]: in a nice regular graph, swapping 1's and 3's by a proper 3-labelling results in another proper 3-labelling.

While this phenomenon is not true in general, designing proper labellings where labels are assigned about the same number of times is caught by the notion of equitable proper labellings, first introduced in [START_REF] Baudon | Equitable neighbour-sum-distinguishing edge and total colourings[END_REF]. Formally, a proper labelling ℓ of a nice graph G is said equitable if |nb(ℓ, i)nb(ℓ, j)| ≤ 1 for any two labels i and j assigned by ℓ. We can then define χ Σ (G) as the smallest k ≥ 1 such that equitable proper k-labellings of G exist.

These notions relate to our problem as follows:

Observation 2.3. If a graph G admits an equitable proper k-labelling ℓ where nb(ℓ, 1) > 0,

then maxOne(G, k) ≥ ⌊ 1 k |E(G)|⌋ and, thus, maxOne(G) ≥ ⌊ 1 k |E(G)
|⌋ Regarding the parameter maxOne, Observation 2.3 makes the most sense for graphs admitting equitable proper k-labellings where k is small. The results of [START_REF] Baudon | Equitable neighbour-sum-distinguishing edge and total colourings[END_REF] actually suggested that an equitable version of the 1-2-3 Conjecture (stating that χ Σ (G) ≤ 3 holds for most graphs G) might be true, which was formalised in [START_REF] Bensmail | Further Results on an Equitable 1-2-3 Conjecture[END_REF]. If proved to hold, that conjecture would thus somewhat imply that maxOne(G) ≥ ⌊ 1 3 |E(G)|⌋ holds for most graphs G. For the record, the authors of [START_REF] Baudon | Equitable neighbour-sum-distinguishing edge and total colourings[END_REF] proved that χ Σ (G) ≤ 2 holds for any nice forest G, that χ Σ (G) = χ Σ (G) ≤ 2 holds for any nice complete bipartite graph G different from K 3,3 (for which labels 1, 2, 3 are needed and sufficient in the equitable version), and that χ Σ (G) = χ Σ (G) = 3 holds for any nice complete graph G different from K 4 (for which labels 1, 2, 3, 4 are needed and sufficient in the equitable setting). It turns out that, to date, K 4 is the only know connected graph G with χ Σ (G) ≥ 4. In [START_REF] Bensmail | On the Role of 3s for the 1-2-3 Conjecture[END_REF], among other things, the authors established that there exist infinitely many graphs G with 2 = χ Σ (G) < χ Σ (G) = 3. Actually, deciding whether χ Σ (G) = 2 holds for a given graph G with χ Σ (G) = 2 is an NP-complete problem. To date, the main open problem regarding the parameter χ Σ (G) is establishing a constant upper bound for any nice graph G. The best upper bound that has been established at this point is χ Σ (G) ≤ |E(G)|, which follows from investigations on a local version of the Antimagic Labelling Conjecture [START_REF] Bensmail | On a combination of the 1-2-3 Conjecture and the Antimagic Labelling Conjecture[END_REF].

Proper labellings with minimum label sum

In [START_REF] Bensmail | On Proper Labellings of Graphs with Minimum Label Sum[END_REF], the authors considered a variant of proper labellings where the sum of assigned labels must be as small as possible. Formally, given a nice graph G and a labelling ℓ of G, one can define σ(ℓ) as the sum of the labels assigned by ℓ to the edges of G. Now, for any k ≥ 1, we define minLabelSum(G, k) as the smallest value of σ(ℓ) for a proper k-labelling ℓ of G, and minLabelSum(G) as the minimum value of minLabelSum(G, k) for some k ≥ 1.

As will be proved later in Section 3, while this might seem natural, it turns out that, in general, minimising the label sum by a proper labelling does not necessarily require to maximise 1's, and vice versa. Still, there are contexts in which these two problems are equivalent, namely when very few different labels are assigned: Observation 2.4. For proper 2-labellings, minimising the label sum is equivalent to maximising 1's. Hence, for any nice graph G and proper 2-labelling ℓ with nb(ℓ, 1)+2⋅nb(ℓ, 2) = minLabelSum(G, 2), we have maxOne(G, 2) = nb(ℓ, 1) and, thus, maxOne(G) ≥ nb(ℓ, 1).

The main results from [START_REF] Bensmail | On Proper Labellings of Graphs with Minimum Label Sum[END_REF] deal mainly with a conjecture the authors raised, stating that we should have minLabelSum(G) ≤ 2|E(G)| for any nice connected graph G. Note that this would hold if one proved that any such G always admits a proper 3-labelling where the number of assigned 1's is always more than the number of assigned 3's, which shows that all variants we have mentioned up to this point are sort of all connected.

The authors of [START_REF] Bensmail | On Proper Labellings of Graphs with Minimum Label Sum[END_REF] determined the parameter minLabelSum for several graph classes, including nice complete bipartite graphs, nice complete graphs, and nice cycles. They also proved that determining minLabelSum(G, 2) for a given graph G is NP-complete, which, due to Observation 2.4, implies that determining maxOne(G, 2) for a given graph G is also NP-complete. Likewise, they proved that the same problem can be solved in polynomial time when G has bounded treewidth, and this yields a similar result in our context. They also proved that, in general, the smallest k ≥ 1 such that minLabelSum(G, k) = minLabelSum(G) is not bounded by a constant, in the sense that, in order to minimise the label sum, it is sometimes necessary to assign arbitrarily large labels. Finally, they provided some upper bounds on minLabelSum(G) for G lying in certain graph classes (nice connected bipartite graphs, nice trees, nice connected graphs with bounded chromatic number, etc.). In particular, they proved that every nice tree admits a proper 2-labelling where the number of assigned 1's is at least the number of assigned 2's; Observation 2.4 thus implies that we have maxOne(T ) ≥ maxOne(T, 2) ≥ ⌈ 1 2 |E(T )|⌉ for every nice tree T .

General behaviour of maxOne

In this section, we give hints on the general behaviour of the parameter maxOne. In particular, we prove that maximising 1's by a proper labelling can require to assign arbitrarily large labels. We also prove that maximising 1's is not equivalent to one of the other related labelling problems we mentioned earlier (minimising the label sum, and minimising 3's in proper 3-labellings). All this leads us to raising a general conjecture, Conjecture 3.6, on the number of 1's we can assign in all nice graphs, by a proper labelling.

On the possible magnitude of maxOne

We start off by remarking that, in some contexts, maximising the number of assigned 1's might require to design proper k-labellings with k arbitrarily large. Theorem 3.1. For arbitrarily large values of k, there exist nice connected graphs G such that maxOne(G) = maxOne(G, k), and maxOne(G, i) < maxOne(G, k) for every i < k.

Proof. Consider the following construction (see Figure 1). Start from an edge uv. Now, choose any α ≥ 2, and add α new vertices x 1 , . . . , x α adjacent to u, as well as α + 1 new vertices y 1 , . . . , y α+1 adjacent to v. Finally, add new degree-1 vertices adjacent to the x i 's and y i 's so that d(x 1 ) = α + 1, d(y 1 ) = α + 2, d(y 2 ), . . . , d(y α+1 ) are α + 3, . . . , 2α + 2, and d(x 2 ), . . . , d(x α ) are 2α + 2, . . . , 3α. Let G denote the resulting graph (actually a tree).

Note that

d(u) = d(x 1 ) = α+1 and d(v) = d(y 1 ) = α+2. Thus, G is not locally irregular, and maxOne(G) < |E(G)| (while |E(G)| = 1 + ∑ 2α+2 i=α+1 i + ∑ 3α i=2α+2 i = 4α 2 + 3α + 3). We claim that maxOne(G) = |E(G)| -1,
and that, by any proper labelling of G assigning label 1 to all but one edge, the unique label different from 1 must be assigned to uv. Note indeed that if the unique label different from 1 was assigned to an edge incident to one of the x i 's, then we would have σ(v) = σ(y 1 ) = α + 2 and the labelling would actually not be proper. Likewise, we would have a similar conclusion if the unique label different from 1 was assigned to an edge incident to one of the y i 's (we would get σ(u) = σ(x 1 ) = α + 1). Thus, the unique label different from 1 must be assigned to uv.

Remark now that upon assigning some label i > 1 to uv and label 1 to all other edges of G, we get {σ(y 1 ), . . . , σ(y α+1 )} = {α +2, . . . , 2α +2}, while d(v) = α +2. Thus, so that we do not get a conflict involving v and one of the y i 's, we must have i > α+1 so that σ(v) > 2α+2. Similarly, we get {σ(x 2 ), . . . , σ(x α )} = {2α+2, . . . , 3α}. Thus, since d(u) = α+1, so that we do not get a conflict between u and the x i 's, it must be that i does not lie in {α+2, . . . , 2α}. Altogether, we thus deduce that we must have i > 2α. The claim now follows from the fact that α can be chosen arbitrarily large.

Maximising 1's versus minimising the label sum

Recall that Theorem 3.1 is one of the main reasons why the two parameters maxOne and minThree are hardly comparable in general. The parameter minLabelSum, however, is subject to a similar behaviour, and one could thus wonder whether, in general, minimising the label sum by a proper labelling is somewhat equivalent to maximising 1's. While this is true in specific contexts (recall Observation 2.4), we prove this is not the case in general. Theorem 3.2. There are nice connected graphs for which any proper labelling maximising the number of 1's is arbitrarily far from minimising the label sum.

Proof. This can be seen through the construction (illustrated in Figure 1) we provided in the proof of Theorem 3.1. For such a graph G (and some α ≥ 2), recall that, by a proper labelling ℓ with nb(ℓ, 1) as large as possible, we have nb(ℓ, 1)

= |E(G)| -1 and ℓ(uv) ≥ 2α + 1; thus, such a proper labelling satisfies σ(ℓ) ≥ |E(G)| + 2α = 4α 2 + 5α + 3. Meanwhile, it can be noticed that one can construct a proper 2-labelling ℓ ′ of G with σ(ℓ ′ ) = |E(G)| + 2 = 4α 2 + 3α + 5.
Indeed, to obtain such an ℓ ′ , it suffices to assign label 2 to any (pendant) edge incident to x 1 different from x 1 u, label 2 to any (pendant) edge incident to y 1 different from y 1 v, and label 1 to all other edges. This indeed results in ℓ ′ being proper, as we get σ(z) = d(z) for all z ∈ V (G) with d(z) ≥ 2 and z / ∈ {x 1 , y 1 }, and the only pairs of adjacent vertices of G with the same degree are {u, x 1 } and {v, y 1 }. In particular, recall as well that degree-1 vertices cannot be in conflict with their unique neighbour, upon assigning strictly positive labels. The full claim now follows from the fact that α can be chosen arbitrarily large in the construction of G.

Regarding the proof of Theorem 3.2, note that minimising the label sum by a proper labelling of the graphs G we construct can still be achieved through assigning label 1 to all but two edges of G, which is very close to maximising the number of 1's. For completeness, below we prove a similar result for the other direction; namely, we prove that there exist graphs in which minimising the label sum is far from maximising 1's.

Theorem 3.3. There are nice connected graphs for which any proper labelling minimising the label sum is arbitrarily far from maximising the number of 1's.

Proof. Let Q denote the graph (depicted in Figure 1(a)) constructed in the proof of Theorem 3.1 for α = 2. Note that |E(Q)| = 25, and, by earlier arguments, we have

minLabelSum(Q) = minLabelSum(Q, 2) = |E(Q)| + 2 = 27.
Indeed, a proper labelling of Q assigning label 1 to all edges but one needs to assign a label with value at least 5 to uv, while we can produce a proper 2-labelling of Q that assigns label 2 to only two edges (and label 1 to the rest). Thus, by any proper labelling ℓ of Q minimising the label sum, we have nb(ℓ, 1)

≤ |E(Q)| -2 = 23, while maxOne(Q) = maxOne(Q, 5) = |E(Q)| -1 = 24.
Now choose any q ≥ 7, and consider the following graph G with 25q edges. Start from q vertex-disjoint copies Q 1 , . . . , Q q of Q. For every i ∈ {1, . . . , q}, let z i denote, in Q i , any one of the two degree-1 vertices adjacent to x 1 (which, recall, has degree 3). Finally, identify all of z 1 , . . . , z q to a single vertex r to get our G. Note that G is, in some sense, a star with q branches, each of which is actually a copy of Q.

Since d(r) = q ≥ 7 and all neighbours of r are of degree 3, note that, by any 2-labelling of G, we cannot have a conflict involving r and one of its neighbours. Also, due to its structure, designing a proper labelling of G with specific properties mainly falls down to designing proper labellings with the same properties in Q 1 , . . . , Q q . In particular, we have

minLabelSum(G) ≤ minLabelSum(G, 2) ≤ q ⋅ minLabelSum(Q, 2) = 27q
and any proper 2-labelling ℓ with minimum label sum of G verifies nb(ℓ, 1) ≤ 23q. On the other hand, we have maxOne(G) ≥ q ⋅ maxOne(Q) = 24q.

The desired conclusion then arises from the fact that q can be chosen arbitrarily large.

Remark that the construction used in the proof of Theorem 3.3 could also be used to prove Theorem 3.2. An important difference, however, is that, for graphs from the former construction, maximising 1's requires at least the use of label 1, . . . , 5, while for those from the latter construction this requires only the use of labels 1 and 2. Thus, the two constructions achieve slightly different goals.

Maximising 1's versus minimising 3's

Due to Theorem 3.1 and our arguments from Section 2, maximising 1's and minimising 3's can only be compared in the context of proper 3-labellings. Still, we establish that, even in the context of proper 3-labellings, these two problems are sometimes quite different. Theorem 3.4. There are nice connected graphs for which any proper 3-labelling maximising the number of 1's is arbitrarily far from minimising the number of 3's, and vice versa.

Proof. This can be established through a slight modification of the graphs we considered in the proofs of Theorems 3.2 and 3.3. Let Q be the graph with 45 edges depicted in Figure 2. Below, we deal with the vertices and edges of Q through the notation given in that figure. Note that Q is not locally irregular, since it has four pairs of adjacent vertices with the same degree (namely, {v 1 , v 3 }, {v 4 , v 5 }, {v 6 , v 7 }, and {v 8 , v 9 }). Also, due to the structure of Q, and due to these pairs, we have maxOne(Q) ≤ |E(Q)| -2 = 43, and, clearly, any proper labelling ℓ of Q assigning label 1 to all but two edges must assign a label different from 1 to v 3 v 4 and v 7 v 8 . Actually, to avoid any conflict between v 3 and v 1 and v 2 , and similarly between v 8 and v 9 and v 10 , we must have ℓ(v 3 v 4 ), ℓ(v 7 v 8 ) ≥ 3. Thus, the unique proper 3-labelling ℓ of Q maximising the number of assigned 1's assigns label 3 to v 3 v 4 and v 7 v 8 and label 1 to the rest (it can be checked that this is indeed proper). Thus, we have maxOne(Q, 3) = 43, and this ℓ satisfies

σ(ℓ) = |E(Q)| + 4 = 49.
On the other hand, we have minLabelSum(Q) ≤ minLabelSum(Q, 2) ≤ |E(Q)| + 3 = 48. Indeed, one can obtain a proper 2-labelling ℓ of Q by assigning label 2 to any pendant edge incident to v 1 , to any pendant edge incident to v 9 , and to v 5 v 6 (thus to only three edges), and label 1 to the other edges. Furthermore, this ℓ satisfies nb(ℓ, 1)

= |E(Q)| -3 = 42.
Now choose any q ≥ 9, and, just as in the proof of Theorem 3.3, consider the graph G with 45q edges obtained from q copies Q 1 , . . . , Q q of Q by identifying q degree-1 neighbours of the local copies of v 1 to a single vertex r (so that G is a kind of star with q branches each of which is a copy of Q, and all neighbours of r have degree 3). Once more, note that, by any proper 3-labelling of G, it cannot be that r is involved in a conflict; thus, any proper 3-labelling of G is, essentially, a combination of proper 3-labellings of Q 1 , . . . , Q q . Now, by earlier arguments, we have

minLabelSum(G) ≤ minLabelSum(G, 2) ≤ q ⋅ minLabelSum(Q, 2) = 48q,
and any proper 2-labelling ℓ with minimum label sum of G verifies nb(ℓ, 1) ≤ 42q. Meanwhile, we have maxOne(G) ≥ maxOne(G, 3) ≥ q ⋅ maxOne(Q, 3) = 43q, and any proper 3-labelling ℓ of G maximising 1's satisfies σ(ℓ) = 49q. So, by considering large enough values of q, we get that, in G, a proper 3-labelling maximising 1's is arbitrarily far from minimising the label sum, and vice versa. We thus have our conclusion.

A conjecture

Due to the previous results, minimising the label sum and maximising 1's by a proper labelling can then be perceived as rather distant problems, and, in particular, problems we might raise regarding the parameter maxOne do not have to be necessarily reminiscent of existing ones for the parameter minLabelSum. In [START_REF] Bensmail | On Proper Labellings of Graphs with Minimum Label Sum[END_REF], the leading conjecture states that we should have minLabelSum(G) ≤ 2|E(G)| for every nice graph G, formalising the intuition that we should always be able to design proper 3-labellings ℓ of G where nb(ℓ, 1) is about nb(ℓ, 3). Other questions in [START_REF] Bensmail | On Proper Labellings of Graphs with Minimum Label Sum[END_REF] are on proper 2-labellings of nice bipartite graphs. That is, it is believed that there is some c ≥ 1 such that, for every bipartite graph G with χ Σ (G) ≤ 2, we should have minLabelSum(G, 2) ≤ 3 2 |E(G)|+c, or, in other words, that we should always be able to assign labels 1 and 2 to about as many edges. An interesting point lies in the fact that those concerns involve assigning different labels about the same number of times, which sort of connects to equitable proper labellings as considered in [START_REF] Baudon | Equitable neighbour-sum-distinguishing edge and total colourings[END_REF].

To guide our upcoming investigations on the parameter maxOne, we first need to wonder about the existence of "bad" graphs for this parameter, namely nice graphs in which, by any proper labelling, we cannot assign label 1 to too many edges. Examining small graphs leads to considering K 3 , the complete graph on three vertices, which clearly verifies maxOne(K 3 ) = maxOne(K 3 , 3) = 1 = 1 3 |E(K 3 )|. This example is very particular, however, due to its very limited size (maxOne(K 3 ) can also be written as ⌊ 1 2 |E(K 3 )|⌋) and structure. Many other small graphs G actually verify maxOne(G) = 1 2 |E(G)|, which turns out to be a general phenomenon, as exposed by the next result. Proof. Let us start with a straight observation. Let H be a graph containing a path P = uv 1 . . . v p w for some p ≡ 3 mod 4 (thus with length 0 modulo 4), where the v i 's all have degree 2 in H. For any two adjacent vertices v i v i+1 of P , note that, by any proper labelling of H, so that σ(v i ) ≠ σ(v i+1 ), it must be that the two edges incident to v i and v i+1 being at distance 2 (thus different from v i v i+1 ) get assigned distinct labels. In particular, if some edge of P is assigned label 1, then there is another edge of P at distance 2 that cannot be assigned label 1. Due to the fact that the length of P is a multiple of 4, we thus deduce that, by any proper labelling of H, at most half the edges of P can be assigned label 1.

Back to proving Theorem 3.5, consider any graph H, and let G be the (nice) graph obtained from H by considering every edge e of H in turn, and subdividing e n e ≥ 3 times, for some n e ≡ 3 mod 4. As a result, note that, in G, every edge e of H gets transformed into a path P e whose length n e + 1 is a multiple of 4. By the previous observation, by any proper labelling of G, it must be that, in any such path P e , at most half the edges are assigned label 1, while the P e 's partition the edges of G, and G has even size. Thus, we have maxOne(G) ≤ 1 2 |E(G)|, and the claim follows from the fact that the n e 's can be chosen arbitrarily large, as long as they are congruent to 3 modulo 4.

Note that Theorem 3.5 also adapts to various graph classes and properties, provided they comply with the subdivision operation we use. In particular, the result also holds for nice graphs with bounded maximum degree or arbitrarily large girth, for nice planar graphs, etc. Also, while subdividing all edges of H as described in the proof of Theorem 3.5 always results in G being bipartite, we can obtain a very close result for nice non-bipartite graphs by considering a non-bipartite graph as H, and subdividing (as described above) all its edges but any one edge f belonging to an odd-length cycle. Doing so, as a result we get a G that has odd-length cycles (all going through f ), such that maxOne(G) is, at best, just above 1 2 |E(G)|. Thus, Theorem 3.5 is not specific to nice bipartite graphs. For these reasons, we believe the following might hold: Conjecture 3.6. If G is a nice connected graph, then maxOne(G) ≥ ⌈ 1 2 |E(G)|⌉ -1. Again, Conjecture 3.6, if true, would probably not bring anything new regarding the main conjectures from [START_REF] Bensmail | On Proper Labellings of Graphs with Minimum Label Sum[END_REF] on the parameter minLabelSum, since, as emphasised earlier, maximising 1's by a proper labelling can require to employ arbitrarily large labels, which might result in large label sum, or, to the least, larger than the best we can hope for. It is worth pointing out also that the bound in Conjecture 3.6 is expressed so that it fits with some of the results (Theorem 4.2, in particular) to be established in upcoming Section 4. k-labelling of C is then equivalent to finding a proper k-vertex-colouring of G, the graph obtained from C by adding a vertex v e i for every edge e i of C, and adding an edge joining two vertices v e i and v e j if and only if e i and e j are at distance 2 in C. Moreover, assigning the most 1's by a proper labelling of C is then equivalent to finding a proper vertexcolouring of G where a given one of the colours is assigned to the most vertices.

Observe, now, that G is either the disjoint union of two paths of length 1 (when |E(C)| = 4), the disjoint union of two even-length cycles (when |E(C)| is a multiple of 4 at least 8), the disjoint union of two odd-length cycles (when |E(C)| ≡ 2 mod 4), or an odd-length cycle (otherwise, when |E(C)| is odd). The cardinality of the maximum independent sets in such easy structures are easy to deduce, and it can be noted that they lead to the equalities from the statement. Also, any such maximum independent set can be converted to a proper 2-vertex-colouring or proper 3-vertex-colouring of G (depending on the length of C), which, in turn, converts to a proper 2-labelling or proper 3-labelling, respectively, of C, that maximises the number of 1's. For the record, it is indeed known that χ Σ (C) = 2 if |E(C)| ≡ 0 mod 4, while we have χ Σ (C) = 3 otherwise (see e.g. [START_REF] Chang | Vertex-coloring edge-weightings of graphs[END_REF]).

Theorem 4.3. If K n,m is a nice complete bipartite graph with parts of size n and m, then

• maxOne(K n,m ) = maxOne(K n,m , 1) = |E(K n,m )| if n ≠ m; and • maxOne(K n,m ) = maxOne(K n,m , 2) = |E(K n,m )| - √ |E(K n,m )| otherwise.
Proof. If n ≠ m, then K n,m is locally irregular, and the claim follows from the fact that a proper labelling results when assigning label 1 to all edges. Now, assume n = m (with n, m ≥ 2 as otherwise K n,m would not be nice). Since all vertices of K n,m have the same degree, so that we do not have a conflict between two (adjacent) vertices from different parts, it must be that at least n edges are not assigned label 1 (as, otherwise, we would deduce that, in both parts, there is a vertex with sum n). Thus, maxOne(K n,m ) ≤ |E(K n,m )|n (while |E(K n,m )| = n 2 ). Now, by choosing any vertex v of K n,m , assigning label 2 to all edges incident to v, and label 1 to all other edges, we clearly obtain a proper labelling ℓ. Furthermore, nb(ℓ, 1) = |E(K n,m )|n, and the claimed equality thus holds.

General techniques and other graph classes

We here come up with general tools and techniques for designing proper labellings assigning many 1's, which, depending on the graphs considered, can be of varying efficiency. Applying these, we get to determining the exact value of maxOne for a few other graph classes, such as nice complete graphs and more generally dense enough nice graphs.

Special subgraphs

Let G be a graph. For a subset F ⊆ E(G) of edges of G, we say that the corresponding subgraph H (i.e., with edge set F ) of G is special if it fulfils the following properties: The main idea behind special subgraphs is that if H is a special subgraph over edge set F of some graph G, then we can design a proper labelling of G assigning label 1 to all edges in E(G) ∖ F . This is due to the following lemma: Lemma 5.1. Let G be a nice graph, and H be a special subgraph of G defined over some edge set F ⊆ E(G). Assume ℓ is a partial labelling of G where only the edges of E(G) ∖ F are labelled, all with label 1. Then, it is possible to extend ℓ to a proper labelling of G by assigning labels to the edges of F (and preserving the labels of the edges in E(G) ∖ F ).

Proof. For every vertex v of G, let us denote by s(v) the number of its incident edges in E(G) ∖ F . Then, by ℓ, we currently have σ(v) = s(v). At this point, note also that only the isolated vertices of H have all their incident edges labelled, and, if u and v are two such adjacent vertices of G, then, by definition, we have d G (u) ≠ d G (v), and σ(u) ≠ σ(v).

We now explain how to label the edges of F . Start by considering every edge uv ∈ F that forms a single-edge connected component of H. By definition, recall that

d G (u) -d H (u) ≠ d G (v) -d H (v), so s(u) ≠ s(v)
, and, since uv is the only edge incident to u and v that remains to be labelled, note that, when assigning a label to uv, we only need to make sure u does not get in conflict with any of its neighbours other than v, and vice versa. By arguments used to prove Proposition 2.1, we can always find such a label (since we can assign arbitrarily large ones) we can properly assign to uv, to be done with it. We apply the same to every other such isolated edge of H.

It now remains to label all edges of the connected components of H with at least two edges. We treat every such connected component C in the following way. Let T be a spanning tree of C, and r be any vertex of T with degree at least 2 (in T ). We start by assigning label 1 to all edges in E(C) ∖ E(T ). It now remains to label all edges of T . Note that every vertex of C is incident to an edge of T . To label these edges, we consider them in decreasing order e m , . . . , e 1 of their distance to r in T ; in other words, we treat them in reverse order as the edges of T are traversed during a BFS algorithm from r.

We first explain how to deal with all edges e m , . . . , e 3 , before explaining how to deal with e 2 and e 1 , as these edges require some extra care. Assume all edges e m , . . . , e i+1 , for some i ≥ 3, have been treated (and thus labelled), and now consider e i . Assume e i = uv, where, in T , u is closer to r than v is. Due to the ordering we have been considering, and because T is a tree, note that, upon labelling e i , we will completely determine σ(v) (while σ(u) will be determined later on). Thus, the label assigned to e i must be chosen so that v does not get in conflict with any other adjacent vertex of G whose all incident edges have already been assigned a label. Since there are at most ∆(G) -1 such vertices, there is thus a label in {1, . . . , ∆(G)} we can assign to e i without raising any conflict involving v. Then we are done with e i .

Assuming now we already dealt with all of e m , . . . , e 3 , we now deal with e 2 . The point is that, once e 2 is treated, only one edge, e 1 , remains to be labelled, so, when labelling e 2 , we need to make sure that we do not create a conflicting situation that cannot be resolved upon labelling e 1 . Since, recall, we chose r so that d T (r) ≥ 2, it must be that e 2 and e 1 are both incident to r. Assume e 2 = ru and e 1 = rv, where u ≠ v. Upon labelling e 2 , note that we completely determine σ(u), which must not be in conflict with any of its neighbours other than r in G. Also, note that, upon labelling e 2 , we would not be able to eventually (through labelling e 1 ) avoid σ(r) = σ(v) if the resulting partial sums of r and v (i.e., the sums of the labels assigned to their incident edges that have been labelled at this point) were the same. So, upon labelling e 2 , we also need to guarantee r and v do not get the same resulting partial sum. Again, there is at least one label in {1, . . . , ∆(G) + 1} that can be properly assigned to e 2 here, so that we do not run into that issue.

It now remains to label e 1 = rv, which will fully determine σ(r) and σ(v). Recall that, when dealing with e 2 , we made sure that the current partial sums of r and v are different, which means that assigning any label to e 1 cannot result in r and v being in conflict. So, we only need to make sure that r does not get in conflict with its at most ∆(G) -1 neighbours other than v in G, and similarly for v and its other at most ∆(G) -1 neighbours in G. Again, by arguments used in the proof of Proposition 2.1, there is at least one proper label in {1, . . . , 2∆(G) -1} we can assign to e 1 , to be done with C. By then treating all other connected components with at least two edges of H this way, we end up with the desired proper labelling of G.

Regarding maximising 1's by a proper labelling, due to Lemma 5.1, we would definitely be more interested in graphs admitting special subgraphs over the least edges possible (so that the number of other edges, to which we would assign label 1, is maximised). Consequently, for any graph G, we define MSS(G) as the number of edges of the largest special subgraph of G. The following now clearly holds.

Corollary 5.2. For every nice graph G, we have maxOne(G) ≥ |E(G)| -MSS(G).

Note that the parameter MSS(G) is well defined for every nice graph G. In particular, it can be noted that any spanning tree of a nice connected graph forms a special subgraph. Finding the best special subgraph of a given nice graph, however, does not seem as an easy task in general, as, recall, we are also allowed to have isolated vertices in the subgraph (as long as they are not adjacent and have the same degree in the original graph), as well as isolated edges (as long as their two ends have different degrees in the original graph).

This being said, the fact that any spanning tree of a nice connected graph G forms a special subgraph implies the following side result:

Theorem 5.3. If G is a nice connected graph, then maxOne(G) ≥ |E(G)| -(|V (G)| -1). Corollary 5.4. Nice connected graphs G with |E(G)| ≥ 2(|V (G)|-1) satisfy Conjecture 3.6.
In particular, Corollary 5.4 implies Conjecture 3.6 for sufficiently dense nice graphs, such as graphs with minimum degree at least 4.

For specific graph classes, special subgraphs are actually crucial to understand the parameter maxOne. We illustrate this through nice complete graphs, proving that, K 3 apart, they all comply with Conjecture 3.6. We indeed consider complete graphs on at least four vertices, as K 3 is a cycle and was thus treated earlier through Theorem 4.2.

Theorem 5.5. If K n is a complete graph with n ≥ 4, then

• maxOne(K n ) = |E(K n )| -2 3 (n -1) if n ≡ 1 mod 3; • maxOne(K n ) = |E(K n )| -( 2 3 (n -2) + 1) if n ≡ 2 mod 3; and • maxOne(K n ) = |E(K n )| -( 2 3 (n -3) + 2) otherwise. Proof.
We apply the approach developed through Lemma 5.1 and Corollary 5.2. In the case of a complete graph K n , note that a special subgraph can contain at most one isolated vertex, and that none of its connected components can contain a single edge. Furthermore, it is not too hard to see that, so that a special subgraph of a complete graph has the least edges, there must be exactly one isolated vertex, and all other vertices should, as much as possible, be part of connected components containing two edges only.

From these arguments, consider the subgraph H with edge set F of any complete graph K n (with n ≥ 4) being obtained as follows, where v 1 , . . . , v n denote the vertices of K n .

• If n ≡ 1 mod 3, then add v 2 v 3 and v 3 v 4 to F , then v 5 v 6 and v 6 v 7 , then v 7 v 8 and v 8 v 9 , and so on up to v n-2 v n-1 and v n-1 v n . Note that v 1 is the only isolated vertex of H, and that all other vertices are part of connected components being paths of length 2.

• If n ≡ 2 mod 3, then perform the same as in the previous case up to adding v n-3 v n-2 and v n-2 v n-1 to F , and additionally add v n-2 v n to F . The difference with the previous case is that, here, one of the connected components of H, that containing v n , is a star with three leaves.

• If n ≡ 0 mod 3, then perform the same as previously up to adding v n-4 v n-3 and v n-3 v n-2 to F , and additionally add v n-3 v n-1 and v n-3 v n to F . Here, one of the connected components of H, that containing v n-1 and v n , is a star with four leaves.

It is important to mention that these procedures can indeed be achieved properly, since n ≥ 4. Also, it is not too hard to see that

|F | = MSS(K n ), while |F | = 2 3 (n -1) when n ≡ 1 mod 3, |F | = 2 3 (n -2) + 1 when n ≡ 2 mod 3, and |F | = 2 3 (n -3) + 2 when n ≡ 0 mod 3. By Corollary 5.2, maxOne(K n ) is thus at least the claimed values.
Towards a contradiction, assume now that for, say, some n ≡ 1 mod 3 (the other cases can be treated similarly), there is a proper labelling assigning label 1 to more edges, that is, to all but at most 2 3 (n -1) -1 edges. Denote by F the set of these edges. As mentioned earlier, by this labelling there can be at most one isolated vertex, while the other vertices must all be incident to at least one edge of F . Besides, for similar reasons as before, in K n [F ], none of the connected components can contain only one edge. Now, again, the most efficient way for all vertices but at most one to be covered by such connected components in K n [F ], is to have these connected components to be paths of length 2. Thus, we need

|F | ≥ 2 3 (n -1), which is a contradiction, since |F | ≤ 2 3 (n -1) -1.
Let us emphasise that Theorem 5.5 deals with the general version of the parameter maxOne, while it is known, see e.g. [START_REF] Chang | Vertex-coloring edge-weightings of graphs[END_REF], that χ Σ (K n ) = 3 for every n ≥ 3. Thus, one could more specifically wonder about maxOne(K n , 3). We suspect this parameter might behave similarly as minLabelSum(K n ), which is actually minLabelSum(K n , 3), as proved in [START_REF] Bensmail | On Proper Labellings of Graphs with Minimum Label Sum[END_REF].

It is also worth emphasising that deducing bounds on the parameter maxOne through special subgraphs makes more sense for somewhat dense nice graphs. In particular, in the case of sparse nice graphs, such as nice trees, this method is less likely to be efficient.

Irregulators

In the approach developed in the previous section, involving special subgraphs, the main point was to narrow the distinguishing part of designing a proper labelling down to the edges of a small subgraph, so that all other edges of the whole graph get sort of useless and can thus be assigned label 1 freely. We here explore a sort of opposite idea, relying, exploiting the structure of the graph, on assigning label 1 to the most edges possible so that the distinguishing part is satisfied for the most pairs of adjacent vertices possible, and then the remaining edges are assigned labels, so that a proper labelling results.

These ideas can be implemented through the concept of irregulators, introduced in [START_REF] Fioravantes | Complexity of finding maximum locally irregular induced subgraphs[END_REF]. Recall that a locally irregular graph is a graph in which adjacent vertices have different degrees. Now, for a graph G, a set S ⊂ V (G) of vertices is called an irregulator if G -S is locally irregular. In [START_REF] Fioravantes | Complexity of finding maximum locally irregular induced subgraphs[END_REF], the authors investigated the problem of determining the smallest irregulator of a given graph, which parameter we denote by Irr(G) for a given graph G. Note that determining Irr(G) is equivalent to finding the largest locally irregular induced subgraph of G. The authors of [START_REF] Fioravantes | Complexity of finding maximum locally irregular induced subgraphs[END_REF] mainly investigated the general complexity of determining Irr(G) for a given graph G, establishing, on the negative side, NP-hardness results and non-approximation results on the problem. On the positive side, they proved that Irr(G) can be determined in polynomial time provided G is a path, a cycle, a tree, a complete bipartite graph, or a complete graph, and provided FPT results.

Following the aforementioned ideas, we now establish a connection between finding small irregulators and maximising 1's by a proper labelling. Proof. Set H = G-S. We design a labelling ℓ of G as follows. We start by assigning label 1 to all edges in E(H). At this point, for any two adjacent vertices u and v of H, since H is locally irregular we have σ(u) ≠ σ(v). Along what follows, this will be preserved upon labelling the other edges of G (joining two vertices of S, or one of S and one of H).

We first consider all vertices of S that are not adjacent to any other vertex of S (i.e., isolated vertices of G[S]). For every such vertex v, all its incident edges then go to H. We assign labels to these edges so that, whenever labelling any such edge vw (where w ∈ V (H)), we do not introduce any conflict involving w and one of its neighbours. Also, assuming vw 2 and vw 1 are the last two edges incident to v we label (in that order), similarly as in Lemma 5.1, when labelling vw 2 we also make sure v does not get the same partial sum a w 1 , to guarantee that v and w 1 will not be in conflict when labelling vw 1 afterwards. In case v was actually incident to only one edge, then recall that, whatever label we assign to this edge, v cannot get in conflict with its unique neighbour, since G is nice.

We now consider every edge uv where u, v ∈ S and d S (u) = d S (v) = 1. We start by assigning any label to uv, chosen so that if u is incident to only one edge going to H then u does not get the same partial sum as its unique neighbour in H, and similarly regarding v. We then label the edges incident to u and v going to H (such exist since G is nice) similarly as in the previous case, taking into account, when labelling the last edge, that u and v must get distinct sums. In particular, recall that if one of u and v is not incident to any edge going to H (since G is nice, only one of these two vertices can actually satisfy this), then its degree in G is 1, and it cannot be in conflict with its unique neighbour, whatever label be assigned to uv.

It now remains to label the edges of the connected components of G[S] that contain at least two edges. This can be done in a very similar way as what we did in the proof of Lemma 5.1. Let C be a connected component of G[S] with at least two edges, and let T be a spanning tree of C rooted at some vertex r with degree at least 2 (in T ). We first assign label, say, 1 to the edges of E(C) ∖ E(T ). Next we consider the vertices of T in reverse order of their distance to r in T . Whenever considering a new vertex v this way, this means there remains only one incident edge vu in T to be labelled (where u is closer to r than v is), together, possibly, with edges incident to v going to H. We first assign labels to the edges incident to v going to H so that no conflicts involving the neighbours of v arise (which can be done as previously). Last, we label vu, with a label chosen so that the sum of v does not get the same as that of one of its neighbours in H, or of one of its neighbours in T we considered earlier. We are then done with v, and the process can go on.

Just like in the proof of Lemma 5.1, we also need to pay extra attention when labelling the penultimate edge of C, as the label assigned to that edge must guarantee the two ends of the last edge of C to be labelled do not get in conflict.

Altogether, this whole labelling process results in a proper labelling of G where all edges of H are assigned label 1. The claimed bound then follows.

There are cases where the bound in Theorem 5.6 is rather bad, as illustrated by complete graphs, since, clearly, any nice complete graph K n satisfies Irr(K n ) = n-1. Yet, this case is extreme, and, in other cases, such as when local places of a nice graph are locally irregular, it might be that the approach behind Theorem 5.6 is more promising than that involving special subgraphs and Corollary 5.2 (which does not take into consideration that large local places can just be assigned 1's right away by a proper labelling).

On a different note, while finding, in a given graph, a largest induced subgraph satisfying some property is a classical problem, [START_REF] Fioravantes | Complexity of finding maximum locally irregular induced subgraphs[END_REF] did not report concrete applications or problems where finding small irregulators would be useful. To the best of our knowledge, our use of these notions is thus one of its very first applications.

Modulo methods

We now discuss the use of modulo methods, which have been very classical tools for designing proper labellings with specific properties (see e.g. [START_REF] Bensmail | On the Role of 3s for the 1-2-3 Conjecture[END_REF][START_REF] Bensmail | On Proper Labellings of Graphs with Minimum Label Sum[END_REF]). The main idea here is to design proper labellings that allow to distinguish adjacent vertices w.r.t. their sums modulo some fixed value (such as the graph's chromatic number). Such labellings can e.g. be attained by switching labels along paths with particular length.

These ideas lead to the following result, for which we provide an abridged proof (as a proof with full details would follow the exact same lines as in [START_REF] Bensmail | On the Role of 3s for the 1-2-3 Conjecture[END_REF][START_REF] Bensmail | On Proper Labellings of Graphs with Minimum Label Sum[END_REF]).

Theorem 5.7. If G is a (nice) connected non-bipartite k-colourable for some odd k ≥ 3, then maxOne(G) ≥ maxOne(G, k) ≥ |E(G)| -|V (G)|.
Proof. Since G is not bipartite, it contains an odd-length cycle C. We extend C to a particular subgraph H of G, in the following way. We start from H = C. Then, as long as there is a vertex v of G that does not belong to H, we add to H the edges of a shortest path from v to some vertex of H. Once all vertices of G are spanned by H, note that H is a unicyclic spanning subgraph of G, where the unique cycle, C, has odd length. We start building ℓ, a proper labelling of G, by assigning label 1 to all edges of E(G) ∖ E(H). It now remains to label the edges of H. To that end, we consider a proper {0, . . . , k -1}-vertex colouring ϕ (where k ≥ 3 is odd) of G, and label the edges of H so that, eventually, we have σ(v) ≡ ϕ(v) mod k for every vertex v ∈ V (G). For convenience, and because we are considering sums modulo k, in what follows we assign labels in {0, . . . , k -1} to the edges of H, but label 0 can equivalently be regarded as label k.

Start from all edges of H being assigned label, say, 1. Now consider any vertex v of G for which σ(v) / ≡ ϕ(v) mod k (when taking into account the 1's assigned to the edges of E(G) ∖ E(H)), and consider an odd-length closed walk W starting and ending at v, and traversing edges of H only. Such a walk exists because of the presence of C in H. Now, traverse the consecutive edges of W , starting from v and going all the way back to v, and, as going along, apply (modulo k) +1 and -1 alternatively to the labels of the traversed edges. That is, we apply +1 to the first edge, -1 to the second one, +1 to the third one, -1 to the fourth one, and so on. As a result, it can be checked that only the sum of v is altered modulo k, and, due to the length of W , it is actually altered by +2. Since k is odd, we can repeat this process, if necessary, until we get σ(v) ≡ ϕ(v) mod k as desired.

Since we can process any other faulty vertex of G this way, eventually the resulting labelling ℓ of G is proper, and it satisfies that all edges of E(G)∖E(H) are assigned label 1. Note that, in the proof of Theorem 5.7, it is important that the graph is k-colourable for some k ≥ 3 odd. As a corollary, we thus derive the following.

Corollary 5.8. If G is a (nice) connected k-chromatic graph with k ≥ 3, then • maxOne(G) ≥ maxOne(G, k) ≥ |E(G)| -|V (G)| if k is odd; and • maxOne(G) ≥ maxOne(G, k + 1) ≥ |E(G)| -|V (G)| otherwise.
Corollary 5.8 might seem weaker than previous Theorem 5.3. It is worth to emphasise, however, that the proper labellings we design behind Theorem 5.3 for a nice graph G employ large labels (with maximum value around 2∆(G) or so), while, behind Corollary 5.8, the labels used have lower value in general (at most around χ(G) or so). Thus, Corollary 5.8 is somewhat better than Theorem 5.3 regarding the side question of determining the smallest k ≥ 1 such that maxOne(G) = maxOne(G, k) for a given nice graph G.

Other methods

Note that using modulo methods, as described in Subsection 5.3, actually stands as a particular application of special subgraphs. It actually turns out that other well known graph objects can be regarded as special subgraphs, so the approach we introduced in Subsection 5.1 can also be related to other classical graph notions.

For instance, in light of Conjecture 3.6, another approach one could consider, is exploiting maximum cuts to design proper labellings assigning many 1's. Recall that, for a graph G, a cut C = (U, V ) is a bipartition of V (G), and that the size of C is the number of edges of G across the cut (i.e., joining a vertex in U and one in V ). It is a well known fact that any maximum cut of G, i.e., with maximum size, contains at least half the edges of G. Regarding the parameter maxOne, one could thus imagine that, perhaps, in some contexts, a proper labelling could be obtained through assigning label 1 to all edges of a maximum cut, and resolving all conflicts through labelling all remaining edges. A problem with this approach, however, is that, through a maximum cut (U, V ) of a graph G, it might be that G[U ] and G[V ] contain isolated vertices (an extreme case being when G is bipartite), while the isolated vertices of G[U ] and G[V ] induce some structure in G, and, thus, making sure these vertices are not in conflict by some labelling requires to carefully choose the labels assigned to the edges across the cut. In other words, the fact that a labelling of G is proper does not rely solely on the labels assigned in G[U ] and G[V ].

Another illustration of a case where special subgraphs arise, is for traceable graphs. Recall that a graph G is traceable if it contains a Hamiltonian path, i.e., a spanning path. It should be clear that any Hamiltonian path of a nice graph stands as a special subgraph, so, again, Corollary 5.2 would pop up naturally in such a context. More generally speaking, the same would apply for (nice) graphs having a 2-factor, i.e., a collection of spanning vertex-disjoint cycles, or more generally a k-factor for any k ≥ 3, being a spanning kregular subgraph. The same does not necessarily hold for 1-factors, which are exactly perfect matchings, since isolated edges in special subgraphs are somewhat tricky to deal with. Still, there are contexts in which we can take advantage of perfect matchings, for instance in (nice) graphs admitting two edge-disjoint perfect matchings, which, together, yield a special subgraph. As an even more special case, we deduce that, for any k ≥ 3, any (nice) k-regular graph G of class 1 (i.e., with chromatic index k, or, in other words, a partition of the edge set into k perfect matchings) satisfies maxOne(G) ≥ |E(G)| -|V (G)|.

Conclusion

In this work, we have initiated the study of the parameter maxOne, being motivated both by practical concerns (recall the problem of turning a graph into a locally irregular multigraph), and by the fact that this parameter relates to other problems and notions involving proper labellings. The main results we have provided are two-fold, as we both proved that determining maxOne(G) for a given graph G is a problem on its own (in the sense that it has nothing to do with determining other seemingly close parameters), and came up with several tools and arguments to establish bounds on maxOne(G). Regarding the latter aspect, we were mainly motivated by Conjecture 3.6, which we proved true for several classes of graphs. Another interesting aspect is that we established connections between the parameter maxOne and other classical notions and parameters of graph theory.

Many appealing questions and problems remain open at this point, and could be subject to further work. In particular, Conjecture 3.6 is still open, but recall that Corollary 5.4 states that only very sparse nice graphs remain to be considered. Maybe this could be achieved by considering the maximum average degree (mad for short) parameter, where, recall, for a graph G we denote by mad(G) the maximum density of a subgraph of G. Note indeed that nice graphs not covered by Corollary 5.4 have mad at most about 4, while we know Conjecture 3.6 holds for nice graphs with very small mad (trees and cycles). So one could focus on graphs with small mad. One first step could be to consider planar graphs with large girth (i.e., with long shortest cycles) or graphs with bounded maximum degree, which are sparse in general. It might be that this could be achieved through the tools and arguments we imagined in Section 5, but it might be, too, that other ideas are needed. As pointed out in the previous sections, there are contexts where special subgraphs seem like a viable tool to use, while, in other ones, exploiting irregulators seems more promising. It might thus be that combining all our ideas and tools might be the general way to go.

Apart from Conjecture 3.6, another general question of interest could be, for a given nice graph G, to wonder about the smallest k ≥ 1 such that maxOne(G) = maxOne(G, k). Recall that some of the tools and approaches we proposed actually deal with that very question, such as Theorem 5.7. A downside is that this smallest k can be arbitrarily large for a given graph, recall Theorem 3.1. This question is, thus, probably challenging. Another parameter that is natural to consider for a nice graph G is maxOne(G, χ Σ (G)).

Other appealing questions include algorithmic ones. Recall that, due to Observation 2.4, determining maxOne(G, 2) for a given graph G is NP-complete in general. Actually, for any given graph G and any fixed k ≥ 2, we are pretty confident that proofs from [START_REF] Bensmail | On Proper Labellings of Graphs with Minimum Label Sum[END_REF] could be derived to prove that determining maxOne(G, k) is NP-complete. However, the situation is not clear about the complexity of determining maxOne(G) for a given graph G, even when G is a tree, as, even for trees, arbitrarily large labels are sometimes needed in order to maximise 1's by a proper labelling (recall the construction from Theorem 3.1), which property makes it hard to design NP-hardness reductions. This question could also be considered through the following lens. As highlighted throughout Section 5, in many contexts, given a nice graph, we start from a certain set of edges being assigned label 1, and we hope to be able to label the remaining edges so that a proper labelling results. This converts to a general problem, being, for a given graph G that is already partially labelled (with 1's), to extend the labelling to a proper labelling. In view of the approaches we developed, one could naturally wonder about the general complexity of this problem.

All these directions apart, maximising 1's through proper labellings, as mentioned in Section 2, relates to other close problems and notions, such as proper labellings minimising the label sum, minimising 3's by proper 3-labellings, equitable proper labellings, irregulators, etc., to which are related problems that are all interconnected somehow. For all these problems and notions, many aspects remain open, and, due to these interconnections, it might be that progressing on any of them also provides something regarding the others.

3 Figure 1 :

 31 Figure 1: Illustration of the construction in the proof of Theorem 3.1. Pendant edges incident to the xi's and yi's are not drawn. The number in each vertex indicates its actual degree in the whole graph.

Figure 2 :

 2 Figure 2: The graph Q in the proof of Theorem 3.4. Pendant edges incident to some of the vertices are not drawn; the number in each vertex indicates its actual degree in the whole graph.

Theorem 3 . 5 .

 35 There are arbitrarily large nice graphs G with maxOne(G) ≤ 1 2 |E(G)|.

(

  A) if two of its isolated vertices, say u and v, are adjacent in G, then d G (u) ≠ d G (v); (B) no connected component of H with only one edge uv satisfies d G (u) = d G (v).

Theorem 5 . 6 .

 56 If a nice graph G admits an irregulator S, then maxOne(G) ≥ |E(G -S)|.

  Since H is unicyclic, we have |E(H)| = |V (H)| = |V (G)|, and the bound thus follows.

Hence why we consider k-labellings, assigning strictly positive labels.

We say there is a conflict between two vertices u and v by a labelling if σ(u) = σ(v).

Easy classes of graphs

In this section, we investigate the parameter maxOne for easy graph classes, in which the structure is so predictable that the exact value can be determined through straight ad hoc arguments. More precisely, we consider nice paths, nice cycles, and nice complete bipartite graphs. In each case, Conjecture 3.6 is proved to hold. For transparency, let us mention that, here, the proof arguments we employ are close to arguments used in [START_REF] Bensmail | On Proper Labellings of Graphs with Minimum Label Sum[END_REF] to determine minLabelSum for these graphs, the context being very close to that of Observation 2.4. It is also worth mentioning that, for these classes of graphs we consider, the proper labellings we design actually use labels 1, . . . , χ Σ (G) for a graph G. Thus, in other words, Theorem 3.1 would not restrict to these classes of graphs. Proof. If |E(P )| = 2, then P is locally irregular, and we end up with a proper labelling when assigning label 1 to all edges. This proves the first item.

Regarding the other items, note that, regardless of the length of P , if v i , v i+1 , v i+2 , and v i+3 are four consecutive vertices, then, in order to have σ(v i+1 ) ≠ σ(v i+2 ) by a labelling ℓ, we must have ℓ(v i v i+1 ) ≠ ℓ(v i+2 v i+3 ). Recall also that, by any labelling assigning strictly positive labels, a degree-1 vertex cannot be in conflict with its unique neighbour. From these arguments, it is easy to see that, in order to assign the most 1's by a proper labelling of P , one should assign 1's to pairs of subsequent edges, so that the pairs of subsequent edges preceding and succeeding it are not assigned label 1. More formally, if we denote by e 1 , . . . , e m the consecutive edges of P , then, assuming we assign label 1 to a pair {e i , e i+1 } of subsequent edges, the pairs {e i-2 , e i-1 } and {e i+2 , e i+3 } must be assigned other labels.

From these arguments, we deduce that, to assign label 1 to the most edges of P , one can assign label 1 to the edges in the pairs {e 1 , e 2 }, {e 5 , e 6 }, {e 9 , e 10 }, and so on (where, naturally, depending on the length of P , the last pair might contain only one edge). By the arguments above, the other edges, not part of these pairs, can be assigned e.g. label 2. In all cases, we end up with a proper 2-labelling, since no two edges at distance 2 are assigned the same label. Also, this labelling maximises the number of 1's by the previous arguments (as assigning more 1's would imply two edges at distance 2 are assigned label 1), and it can be checked that we have the claimed equalities, depending on |E(P )|.

Proof. This follows from similar reasons as for paths in the proof of Theorem 4.1. In particular, in any proper labelling of C, two edges at distance 2 must always be assigned distinct labels. Denoting by e 1 , . . . , e m , e 1 the consecutive edges of C, finding a proper