We pursue the study of edge-irregulators of graphs, which were recently introduced in [Fioravantes et al. Parametrised Distance to Local Irregularity. IPEC, 2024]. That is, we are interested in the parameter Ie(G), which, for a given graph G, denotes the smallest k >= 0 such that G can be made locally irregular (i.e., with no two adjacent vertices having the same degree) by deleting k edges. We exhibit notable properties of interest of the parameter Ie, in general and for particular classes of graphs, together with parameterized algorithms for several natural graph parameters. Despite the computational hardness previously exhibited by this problem (NP-hard, W[1]-hard w.r.t. feedback vertex number, W[1]-hard w.r.t. solution size), we present two FPT algorithms, the first w.r.t. the solution size plus Delta and the second w.r.t. the vertex cover number of the input graph. Finally, we take important steps towards better understanding the behaviour of this problem in dense graphs. This is crucial when considering some of the parameters whose behaviour is still uncharted in regards to this problem (e.g., neighbourhood diversity, distance to clique). In particular, we identify a subfamily of complete graphs for which we are able to provide the exact value of Ie(G). These investigations lead us to propose a conjecture that Ie(G) should always be at most m/3 + c, where $m$ is the number of edges of the graph $G$ and $c$ is some constant. This conjecture is verified for various families of graphs, including trees.

翻译：我们继续研究图的边非规则化参数，该概念近期在[Fioravantes等人，参数化局部非规则距离，IPEC，2024]中被提出。具体而言，我们关注参数Ie(G)，对于给定图G，该参数表示使得G通过删除k条边后变为局部非规则图（即任意相邻顶点度数均不相同）的最小k值（k≥0）。我们展示了Ie参数在一般图及特定图类中的重要性质，并针对多个自然图参数提出了参数化算法。尽管该问题已被证明具有计算复杂性（NP难解，相对于反馈顶点数为W[1]-难解，相对于解规模为W[1]-难解），我们仍提出了两个FPT算法：第一个算法参数为解规模加Δ，第二个算法参数为输入图的顶点覆盖数。最后，我们为深入理解该问题在稠密图中的行为迈出重要步伐，这对于探究某些尚未明确该问题行为的参数（例如邻域多样性、团距离）至关重要。特别地，我们识别出一个完全图子族，并给出了其Ie(G)的精确值。这些研究促使我们提出猜想：Ie(G)应始终不超过m/3 + c，其中$m$为图$G$的边数，$c$为常数。该猜想已在包括树在内的多类图族中得到验证。