Distinguishing adjacent vertices by ordering edges
Abstract
The 1-2-3 Conjecture states that for every graph without isolated edges, there exists an edge-weighting from {1,2,3} such that adjacent vertices receive distinct sums of weights on their incident edges. In the sequence variant, adjacent vertices are to be distinguished by the sequences of weights on their incident edges. In this paper, we investigate whether, for every graph without isolated edges and for a fixed proper edge colouring (where colours are interpreted as weights), there exists a global total order of the edges such that the resulting sequences of incident weights distinguish adjacent vertices. For connected graphs, we prove that such an order exists whenever there exist two adjacent vertices that have distinct sets of incident weights. This yields a positive answer for every proper edge colouring of a connected non-regular graph or a connected graph of class two. Moreover, a probabilistic argument gives the same conclusion for connected regular graphs of degree at least six.
Related
- Spanning tree with bounded degree sum of two adjacent vertices
- Adjacent vertex distinguishing total chromatic number of graph products
- Large induced subgraphs with k vertices of maximum degree
- Lattice coverings by parallelotopes containing cube vertices
- Focal Sets of the John Ellipsoid of a Simplex from Its Vertices
BibTeX
@misc{gorzkowska2026distinguishing,
title = {{Distinguishing adjacent vertices by ordering edges}},
author = {Aleksandra Gorzkowska and Jakub Kwaśny},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.11832},
eprint = {2609.11832},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.11832},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Distinguishing adjacent vertices by ordering edges
AU - Aleksandra Gorzkowska
AU - Jakub Kwaśny
PY - 2026
DA - 2026/09/10
PB - arXiv
DO - 10.48550/arxiv.2609.11832
UR - https://arxiv.org/abs/2609.11832
AB - The 1-2-3 Conjecture states that for every graph without isolated edges, there exists an edge-weighting from {1,2,3} such that adjacent vertices receive distinct sums of weights on their incident edges. In the sequence variant, adjacent vertices are to be distinguished by the sequences of weights on their incident edges. In this paper, we investigate whether, for every graph without isolated edges and for a fixed proper edge colouring (where colours are interpreted as weights), there exists a global total order of the edges such that the resulting sequences of incident weights distinguish adjacent vertices. For connected graphs, we prove that such an order exists whenever there exist two adjacent vertices that have distinct sets of incident weights. This yields a positive answer for every proper edge colouring of a connected non-regular graph or a connected graph of class two. Moreover, a probabilistic argument gives the same conclusion for connected regular graphs of degree at least six.
ER -