Making Graphs Irregular through Irregularising Walks
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915360044744704 |
|---|---|
| author | Bensmail, Julien Bourneuf, Romain Colinot, Paul Humeau, Samuel Martinod, Timothée |
| author_facet | Bensmail, Julien Bourneuf, Romain Colinot, Paul Humeau, Samuel Martinod, Timothée |
| contents | The 1-2-3 Conjecture, introduced by Karoński, Ł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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2506_21254 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Making Graphs Irregular through Irregularising Walks Bensmail, Julien Bourneuf, Romain Colinot, Paul Humeau, Samuel Martinod, Timothée Discrete Mathematics Combinatorics The 1-2-3 Conjecture, introduced by Karoński, Ł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. |
| title | Making Graphs Irregular through Irregularising Walks |
| topic | Discrete Mathematics Combinatorics |
| url | https://arxiv.org/abs/2506.21254 |