Title: Making Graphs Irregular through Irregularising Walks Show Chinese title

Title: 通过不规则行走使图变得不规则

Abstract: The 1-2-3 Conjecture, introduced by Karo\'nski, {\L}uczak, and Thomason in 2004, was recently solved by Keusch. This implies that, for any connected graph $G$ different from $K_2$, we can turn $G$ into a locally irregular multigraph $M(G)$, i.e., in which no two adjacent vertices have the same degree, by replacing some of its edges with at most three parallel edges. In this work, we introduce and study a restriction of this problem under the additional constraint that edges added to $G$ to reach $M(G)$ must form a walk (i.e., a path with possibly repeated edges and vertices) of $G$. We investigate the general consequences of having this additional constraint, and provide several results of different natures (structural, combinatorial, algorithmic) on the length of the shortest irregularising walks, for general graphs and more restricted classes. Show Chinese abstract

Abstract: 1-2-3猜想，由Karoński、{\L }uczak和Thomason于2004年提出，最近由Keusch解决。这表明，对于任何不同于$K_2$的连通图$G$，我们可以通过将其中的一些边替换为最多三条平行边，将$G$转换为局部不规则多重图$M(G)$，即其中没有两个相邻顶点具有相同的度数。 在本工作中，我们引入并研究了在附加约束条件下的这个问题，即添加到$G$以达到$M(G)$的边必须形成一个走（即可能有重复边和顶点的路径）的$G$。我们研究了这个附加约束的一般后果，并提供了关于最短不规则化走长度的不同性质（结构、组合、算法）的结果，针对一般图和更受限的类别。