On the Graham–Sloane harmonious labelling conjecture

Alp Müyesser, Alexey Pokrovskiy · 2025

Read On the Graham–Sloane harmonious labelling conjecture by Alp Müyesser, Alexey Pokrovskiy (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2509-05280.txt.

Introduction

Labelling tree graphs so edge sums never repeat is solved for a wide class by Alp Müyesser and Alexey Pokrovskiy in a 2025 combinatorics paper. The problem traces to Graham and Sloane in 1980 and asks when tree vertices can take the labels of an abelian group, one-to-one, with all edge sums distinct.

The authors give an exact characterisation for trees of bounded degree, where each vertex has a limited number of neighbours. One consequence is that the cyclic group case always works for such trees. That settles a 1980 conjecture of Graham and Sloane, and a later one from 1987, for this class. The results also bear on the study of graph coverings.

Catalog record

CREATORAlp Müyesser, Alexey Pokrovskiy
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE109 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2509-05280

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

On the Graham–Sloane harmonious labelling conjecture Alp Müyesser, Alexey Pokrovskiy Abstract . Consider an order n n abelian group G G and a tree T T on n n vertices. When is it possible to (bijectively) label V ⁡ ( T ) V(T) by G G so that along all edges x ​ y xy of T T , the sums x + y x+y are distinct? This problem can be traced back to the work of Graham and Sloane on the harmonious labelling conjecture, and has been studied extensively since its introduction in 1980. We give a precise characterisation that holds for all bounded degree trees. In particular, our characterisation implies that if G = ℤ / n ​ ℤ G=\mathbb{Z}/n\mathbb{Z} and T T is a bounded degree tree, the desired labelling exists. This confirms a conjecture of Graham and Sloane from 1980, and another conjecture of Chang, Hsu, and Rogers from 1987, for bounded degree trees. Our results also have further applications for the study of graph coverings. 1. Introduction Graph labelling problems are some of the most well-studied problems in combinatorics. A prototypical and infamous problem in this direction is the Ringel-Kotzig conjecture, or as more popularly known, the graceful tree conjecture, that asserts that the vertices of any n -vertex tree can be (bijectively) labelled by \{0,1,\ldots,n\} , so that along all edges of T , the absolute value of the difference of the labels of x and y are distinct. We refer the reader to the comprehensive survey of Gallian [ 14 ] for an overview of the area. In an influential paper from 1980, motivated by related problems concerning additive bases and error-correcting codes, Graham and Sloane [ 16 ] studied an analogous labelling problem for trees, where the label set is viewed modulo some integer n , and the requirement is that along all edges of the tree, the sum of the labels of x and y are distinct (modulo n ). More precisely, they conjectured the following. Conjecture 1.1 (The harmonious labelling conjecture, [ 16 ] ) . For any n -edge tree T , there exists a labelling \phi\colon V(T)\to\mathbb{Z}_{n} so that for all xy\in E(T) , \phi(x)+\phi(y) attains a distinct value, and furthermore, \phi uses exactly one label on two vertices. This conjecture is known to hold for trees on \leq 31 vertices, caterpillars, and many other special classes of trees (see Chapter 2 in [ 14 ] and the references therein). A relaxation of the conjecture, where the labels come from \mathbb{Z}_{n+o(n)} rather than \mathbb{Z}_{n} , is known to be true due to work of Montgomery, Pokrovskiy, and Sudakov [ 27 ] . This latter result was an important ingredient in the work of the same authors [ 28 ] settling Ringel’s conjecture (see also the independent proof of Keevash and Staden [ 21 ] ) which states that the edges of K_{2n+1} can be decomposed into any n -edge tree T . These last results were originally phrased using the language of rainbow subgraphs which we will also use in this paper. Recall that an edge-coloured graph is called rainbow if each colour appears at most once. Given a graph T and a coloured graph G , a rainbow copy of T in G is a subgraph T^{\prime} of G which is isomorphic to T and all of whose edges have different colours. There are many conjectures that can be rephrased using this definition [ 30 ] . For example the Ringel–Kotzig conjecture mentioned in the first paragraph is equivalent to stating that a rainbow copy of any tree T exists in the colouring of K_{|T|} whose vertices are 1,\dots,|T| with ij coloured by |i-j| . The harmonious labelling conjecture of Graham and Sloane, on the other hand, is equivalent to a rainbow embedding problem where the edge-colouring rule comes from the Cayley-sum graph of a cyclic group. To make this formal, we give the following definition. Definition 1.2 . Let G be an abelian group. We define K_{G} to be the edge-coloured complete graph on vertex set G , where the edge xy is assigned the colour x+y . By definition, an embedding of T on K_{G} gives a rainbow copy whenever the labelling induced by the mapping satisfies that for each edge xy\in G , x+y attains a distinct value. In this paper, we consider embeddings of trees T on K_{G} where |V(G)|=|V(T)| . This informs the harmonious labelling conjecture directly, as it is a more restrictive notion. To see this, let us consider a n -edge, (n+1) -vertex tree T , and let us construct T^{\prime} by deleting an arbitrary leaf v , letting w be the parent of v . Suppose we found a rainbow embedding \phi\colon V(T^{\prime})\to V(K_{\mathbb{Z}_{n}})=\mathbb{Z}_{n} of T^{\prime} in K_{\mathbb{Z}_{n}} . There exists a unique element c\in\mathbb{Z}_{n} not used as a colour along any edge in the embedding given by \phi , so we can then extend \phi to T by defining \phi(v)=c-\phi(w) , meaning that \phi(v)+\phi(w)=c , which implies that the harmonious labelling conjecture holds for T . This brings us to the following natural conjecture, first stated by Chang, Hsu, and Rogers [ 9 ] in 1987, that if true, would directly imply the harmonious labelling conjecture of Graham and Sloane. Conjecture 1.3 (Chang, Hsu, Rogers, [ 9 ] ) . For all n -vertex trees T , K_{\mathbb{Z}_{n}} contains a rainbow copy of T . In this paper, we study a natural generalisation of Conjecture 1.3 where \mathbb{Z}_{n} is a general abelian group. A direct extension of Conjecture 1.3 is not possible in this set-up, due to following well-known construction of Maamoun and Meyniel [ 24 ] from 1984. Example 1.4 . Let T be a n -vertex path where n=2^{k} for some k\geq 2 , and let G=\mathbb{F}_{2}^{k} , then K_{G} contains no rainbow copy of \mathbb{F}_{2}^{n} . Proof. Suppose otherwise and take a bijection \phi\colon V(P_{2^{n}})\to\mathbb{F}_{2}^{n} . The set C consisting of sum of labels along edges must be the set \mathbb{F}_{2}^{n}\setminus\{0\} because 0 does not appear as a colour in K_{G} , since G=\mathbb{F}_{2}^{k} . Denote by v,w the endpoints of the path T . We have 0=\sum\mathbb{F}_{2}^{n}\setminus\{0\}=\sum_{xy\in E(T)}\phi(x)+\phi(y)=\sum_{x\in V(T)}\mathrm{deg}_{T}(x)\cdot\phi(x)=\phi(v)+\phi(w)\neq 0, giving a contradiction. ∎ With a similar proof that we will present formally in Section 5 , we can also show that if T has a rainbow copy in K_{\mathbb{F}_{2}^{k}} (supposing k\geq 2 ), then T cannot have precisely two vertices of even degree. However, these examples barely scratch the surface of the space of possible obstructions. Indeed, there are several other constructions of trees T and abelian groups G where T does not have a rainbow copy in K_{G} . Such constructions are systematically studied in recent work of Jamison and Kinnersley [ 20 ] , and further results are presented in [ 10 ] . The diversity of the constructions present in [ 20 , 10 ] indicates that a full characterisation of when a tree admits a rainbow copy in a given K_{G} is presently out of reach. The contribution of our main result, stated below, is twofold: we find a new class of constructions, and also show that they are

Read the complete text