[SeqFan] A problem about distances on a tree

[谢逸凡]

Dear sequence fans,

I recently came across this problem:

Given a positive integer n. n is good iff there exists a tree on n vertices, and we can label the n-1 edges with positive integers such that the pairwise distances d(A,B) between two vertices A and B (the sum of labels on the path from A to B) form exactly the integers from 1 to n(n-1)/2.

Theorem: n is good implies that n-2 is a square. Proof: Pick a vertice A on the tree. Record the d(A,B), where B ranges from the n-1 remaining vertices. Suppose that the n-1 distances consist of x even numbers and y odd numbers. For vertices B and C different from A, we note that d(B,C) == d(A,B)+d(A,C) (mod 2). So there are exactly y + xy pairwise distances. So we know that x+y = n-1 and (x+1)y = (n(n-1)/2+1)/2. Then it's easy to get n-2 is a square.

The solutions for n = 3 and 6 can be constructed (see the illustration). But the next possible good number is 11, which is hard to give examples or do brute force search.

Can anyone help me with this problem or find out if this is already in the OEIS?

Best regards,

Yifan Xie

[D. S. McNeil]

Fun problem!  But I'm not sure if n-2 needs to be a square.. isn't n=4 good?

          [1]
           |
        (1)|
           |
[2]--(2)--[0]--(4)--[3]


Doug

--
You received this message because you are subscribed to the Google Groups "SeqFan" group.
To unsubscribe from this group and stop receiving emails from it, send an email to seqfan+un...@googlegroups.com.
To view this discussion visit https://groups.google.com/d/msgid/seqfan/CAA%3DdhBxCMdPjSxoE8%2BHmaretnXaqvMTJYz-AOXfXJYm4gk4V%3Dw%40mail.gmail.com.

[Neil Sloane]

That reminds me a bit of the problem of finding a "Graceful labeling"  for a tree. There are many references, many sequences ...

Best regards

Neil 

Neil J. A. Sloane, Chairman, OEIS Foundation.

Also Visiting Scientist, Math. Dept., Rutgers University, 

Email: njas...@gmail.com

To view this discussion visit https://groups.google.com/d/msgid/seqfan/CAOX9QiC%3DCuUE4iSX6oT_eJhZP%2BDoOO-%2Bi6sKK428gubBD7UCDg%40mail.gmail.com.

[David desJardins]

On Wed, Sep 24, 2025 at 3:28 PM 谢逸凡 <oeis....@gmail.com> wrote:

Theorem: n is good implies that n-2 is a square. Proof: Pick a vertice A on the tree. Record the d(A,B), where B ranges from the n-1 remaining vertices. Suppose that the n-1 distances consist of x even numbers and y odd numbers. For vertices B and C different from A, we note that d(B,C) == d(A,B)+d(A,C) (mod 2). So there are exactly y + xy pairwise distances. So we know that x+y = n-1 and (x+1)y = (n(n-1)/2+1)/2. Then it's easy to get n-2 is a square.

I don’t understand the proof at all. But I guess that’s good, because someone has already posted a counterexample.

[Brendan]

Another solution for n=4 is a path with edge lengths 1,3,2.  However this is the largest

solution for a path since it would be a "perfect Golomb ruler" which are known to not

exist for n>4.

This is a nice generalization of the "perfect Golomb ruler" problem.

Brendan.

--

You received this message because you are subscribed to the Google Groups "SeqFan" group.
To unsubscribe from this group and stop receiving emails from it, send an email to seqfan+un...@googlegroups.com.

To view this discussion visit https://groups.google.com/d/msgid/seqfan/CAP%3DxTqPuXSA6PTtWmjQHrcJDinwbu_RvVHCzQ3ZGPgSp5%2BRs5w%40mail.gmail.com.

[Arthur O'Dwyer]

I bet this peters out while still at very low numbers, just like the "perfect Golomb ruler" problem. It wouldn't surprise me if n=2, n=3, n=4, and n=6 are the only solutions.

Consider n=5. Then we're trying to make the sums from 1 to 10 inclusive, using only 4 edges. Can we have two edges with weights 5 and 6? No, because then there would exist some path including both those edges, which would have length at least 11, and our path-lengths can't exceed 10. Likewise we can't use both 4 and 7 in our labeling. This feels difficult.

Yet, you managed to find a solution for n=6...

A quick and dirty Python program finds your solution (and that it is the only solution) for n=6. It tells me that there are no solutions for n=5, n=7, or n=8.

In case it helps someone else: Frank Harary's Graph Theory, pages 233–234, enumerates tree graphs for n=1 through n=10. (That's OEIS A000055.)

–Arthur

To view this discussion visit https://groups.google.com/d/msgid/seqfan/CAJeNNUgLEdKttTHhTp%2Bp3pHSDhQy41XKW-eQSd66NRqFqq0nUA%40mail.gmail.com.

[谢逸凡]

Yes, you are correct. I calculated the number of odd distances wrongly (it should be n(n-1)/4 when n(n-1)/2 is even).

The corrected version is: If n == 2 or 3 (mod 4), then n-2 is a square;

If n == 0 or 1 (mod 4), then n is a square.

Yifan Xie

To view this discussion visit https://groups.google.com/d/msgid/seqfan/CAOX9QiC%3DCuUE4iSX6oT_eJhZP%2BDoOO-%2Bi6sKK428gubBD7UCDg%40mail.gmail.com.

[谢逸凡]

Thanks. Can you compute the next two candidates: n=9 and n=11?

Yifan Xie

To view this discussion visit https://groups.google.com/d/msgid/seqfan/CADvuK0Kowaa%3D_Lq%2BZcQhEW5p%3DsafNLzW6CFFEnaK3ihnpZ-DZg%40mail.gmail.com.

[Arthur O'Dwyer]

On Thu, Sep 25, 2025 at 8:06 AM 谢逸凡 <oeis....@gmail.com> wrote:

Thanks. Can you compute the next two candidates: n=9 and n=11?

I've kicked off n=9, but my quick-and-dirty brute-force Python script is likely to take six days to finish. Someone else might come up with a better way in the meantime.

n=11 is completely out of reach for me.

My script is attached. It hard-codes the 47 different graphs on 9 nodes (from Harary), and then for each graph, for each of the (33 choose 6) plausible combinations of edge weights, if the combination passes another simple test, checks each of the (8!) assignments of weights to edges, and reports if any of those assignments is good. That is: it is really dumb. And on top of that, it's in Python rather than a compiled language. :)

On Wed, Sep 24, 2025 at 3:28 PM 谢逸凡 <oeis....@gmail.com> wrote:

Theorem: n is good implies that n-2 is a square. Proof: Pick a vertice A on the tree. Record the d(A,B), where B ranges from the n-1 remaining vertices. Suppose that the n-1 distances consist of x even numbers and y odd numbers. For vertices B and C different from A, we note that d(B,C) == d(A,B)+d(A,C) (mod 2). So there are exactly y + xy pairwise distances. So we know that x+y = n-1 and (x+1)y = (n(n-1)/2+1)/2. Then it's easy to get n-2 is a square.

> I calculated the number of odd distances wrongly (it should be n(n-1)/4 when n(n-1)/2 is even).

> The corrected version is: If n == 2 or 3 (mod 4), then n-2 is a square;

> If n == 0 or 1 (mod 4), then n is a square.

FYI, I still don't understand the skipped steps in your proof. I do understand:

> Pick a vertice A on the tree. Record the d(A,B), where B ranges from the n-1 remaining vertices. For vertices B and C different from A, we note that d(B,C) == d(A,B)+d(A,C) (mod 2).

That makes sense because either the path BC goes through A, or else it is the difference of AB and AC. Either way, d(B,C) is d(A,B)+d(A,C) (mod 2). But then you say:

> Suppose that the n-1 distances consist of x even numbers and y odd numbers. So there are exactly y + xy pairwise distances.

What is a "pairwise distance" here? There are n(n-1)/2 pairs of nodes in the graph, but I don't see how that relates to x or y here. Maybe if you draw out an example on your n=6 graph, taking the upper left point as A; and then again, taking one of the middle points as A...?

Cheers,

Arthur

[Martin Fuller]

On Thursday, September 25, 2025 at 11:18:46 PM UTC+1 Arthur O'Dwyer wrote:

I've kicked off n=9, but my quick-and-dirty brute-force Python script is likely to take six days to finish. Someone else might come up with a better way in the meantime.

n=11 is completely out of reach for me.

I think there are no solutions for n=9 and n=11. I'll put my Python code at the end (because Google Groups website doesn't give me an option to attach a file). My code uses NetworkX to generate trees and CP-SAT to search for distances.

 

> Suppose that the n-1 distances consist of x even numbers and y odd numbers. So there are exactly y + xy pairwise distances.

What is a "pairwise distance" here? There are n(n-1)/2 pairs of nodes in the graph, but I don't see how that relates to x or y here. Maybe if you draw out an example on your n=6 graph, taking the upper left point as A; and then again, taking one of the middle points as A...?

I think this means there are exactly y + xy unordered pairs of vertices that are an odd distance apart. This comes from 1+x vertices an even distance from A (including A itself) multiplied by y vertices an odd distance from A.

Martin Fuller

import datetime
import itertools
import networkx # https://networkx.org/
from ortools.sat.python import cp_model # https://developers.google.com/optimization/reference/python/sat/python/cp_model

def ordered(a,b):
    return (a,b) if a <= b else (b,a)

def gen_golomb_trees(n):
    """Yield {(a,b):d, ...}. Each item is an edge (a,b) with value d."""
    m = n*(n-1) // 2
   
    for tree in networkx.nonisomorphic_trees(n):
        model = cp_model.CpModel()
        dists = {ordered(a,b):model.NewIntVar(1,m,"d") for a,b in tree.edges}
        pathdists = {(a,b):model.NewIntVar(1,m,"p")
              for b in range(n) for a in range(b)}

        for a,paths in networkx.all_pairs_shortest_path(tree):
            for b,c in paths.items():
                if a < b:
                    model.Add(pathdists[(a,b)] == sum(
                        dists[ordered(i,j)] for i,j in itertools.pairwise(c)))

        model.AddAllDifferent(dists.values())
        model.AddAllDifferent(pathdists.values())
       
        solver = cp_model.CpSolver()
        status = solver.Solve(model)
        if status == cp_model.OPTIMAL or status == cp_model.FEASIBLE:
            yield {(a,b):solver.Value(d) for (a,b),d in dists.items()}
        # Extension: Look for multiple solutions for the same tree?

for n in [3,4,6,9,11]:
    print('n=', n, sep='')
    for t in gen_golomb_trees(n): print(t)
    print(datetime.datetime.now().isoformat())

[谢逸凡]

Thanks a lot.

"I think this means there are exactly y + xy unordered pairs of vertices that are an odd distance apart. This comes from 1+x vertices an even distance from A (including A itself) multiplied by y vertices an odd distance from A": That's correct.

Yifan Xie

--
You received this message because you are subscribed to the Google Groups "SeqFan" group.
To unsubscribe from this group and stop receiving emails from it, send an email to seqfan+un...@googlegroups.com.

To view this discussion visit https://groups.google.com/d/msgid/seqfan/beb5675a-4b6a-4d10-888f-a9fe1c6e28fbn%40googlegroups.com.

[Brendan]

It's always hard to be confident about a program that produces no output, but my C code says there are 1, 1, 1, 2, 0, 1 examples on 1-6 vertices and none at all for 7-14 vertices.

11-14 vertices took 2.4, 28, 331, 3921 seconds on my Mac, respectively.  I will run 15 but it really looks like there are no more.

I didn't iterate over trees.  I started with two adjacent edges and repeatedly added a new vertex with an available length.

Brendan.

To view this discussion visit https://groups.google.com/d/msgid/seqfan/CAA%3DdhBxz0iyyPSp4D8ujJ%2B%2BLBDhPcfx1nL1wLFvA2gHiir%2BgLw%40mail.gmail.com.

[Brendan]

None on 15 vertices (9.3 hours).  I won't run 16 vertices, but if someone wants to spend 4-7 days of cpu time I can send my code.  It needs nauty.

Brendan.