Revision history [back]

If we only want one pair of graphs for each n, we can store less data and stop as soon as one pair is found.

With this in mind, we can adapt @tmonteil's code to the following function:

def one_pair(n=3):
    r"""
    Return a pair of connected graphs on n vertices with same spectral
    radius but different diameter and different number of edges.

    If no such pair exists, nothing is returned.
    """
    from collections import defaultdict
    srdm = defaultdict(dict)
    for g in graphs.nauty_geng('{} -c'.format(n)):
        sr = max(g.adjacency_matrix().eigenvalues())
        d = g.diameter()
        m = g.num_edges()
        if not (d, m) in srdm[sr]:
            for (dd, mm) in srdm[sr]:
                if d != dd and m != mm:
                    return sr, (dd, mm), (d, m), srdm[sr][(dd, mm)], g
            srdm[sr][(d, m)] = g

It comes as no surprise that the efficiency gain is spectacular.

While running the more exhaustive search for up to 8 vertices takes on the order of three minutes:

sage: %time pairs = {n: search(n=n) for n in range(3, 9)}
CPU times: user 2min 27s, sys: 4.33 s, total: 2min 32s
Wall time: 3min 10s

with one_pair it takes on the order of one second:

sage: %time pairs = {n: one_pair(n=n) for n in range(3, 9)}
CPU times: user 441 ms, sys: 161 ms, total: 601 ms
Wall time: 1.03 s

and one_pair can go up to 20 vertices in about 30 seconds:

sage: %time pairs = {n: one_pair(n=n) for n in range(3, 21)}
CPU times: user 20.1 s, sys: 1.36 s, total: 21.4 s
Wall time: 25.5 s

To display some concrete examples, introduce a helper function:

sage: from collections import defaultdict
....: def graph_dict(g):
....:     d = defaultdict(list)
....:     for a, b in g.edges(labels=False):
....:         d[a].append(b)
....:     return dict(d)

and run a loop over the pairs found by one_pair above, whose output is ready to be copy-pasted into Sage to explore the examples further.

sage: for n in range(21):
....:     if n in pairs and pairs[n]:
....:         sr, (da, ma), (db, mb), a, b = pairs[n]
....:         sr = AA(sr)
....:         sr. exactify()
....:         if sr not in QQ:
....:              sr = sr.radical_expression()
....:         mp = sr.minpoly()
....:         print('\nTwo graphs A and B on {} vertices, where'.format(n))
....:         print('A has {} edges and diameter {}, '
....:               'B has {} edges and diameter {},'
....:               .format(ma, da, mb, db))
....:         print('and both have spectral radius r = {} '
....:               '(a root of {}):'.format(sr, mp))
....:         print('A = Graph({})'.format(graph_dict(a)))
....:         print('B = Graph({})'.format(graph_dict(b)))
....:

Two graphs A and B on 6 vertices, where
A has 5 edges and diameter 2, B has 6 edges and diameter 4,
and both have spectral radius r = sqrt(5) (a root of x^2 - 5):
A = Graph({0: [5], 1: [5], 2: [5], 3: [5], 4: [5]})
B = Graph({0: [4, 5], 1: [4, 5], 2: [4], 3: [5]})

Two graphs A and B on 7 vertices, where
A has 6 edges and diameter 2, B has 7 edges and diameter 3,
and both have spectral radius r = sqrt(6) (a root of x^2 - 6):
A = Graph({0: [6], 1: [6], 2: [6], 3: [6], 4: [6], 5: [6]})
B = Graph({0: [5, 6], 1: [5, 6], 2: [6], 3: [6], 4: [6]})

Two graphs A and B on 8 vertices, where
A has 9 edges and diameter 3, B has 10 edges and diameter 4,
and both have spectral radius r = 3 (a root of x - 3):
A = Graph({0: [6, 7], 1: [6, 7], 2: [6], 3: [6], 4: [7], 5: [7], 6: [7]})
B = Graph({0: [6, 7], 1: [6, 7], 2: [6, 7], 3: [6, 7], 4: [6], 5: [7]})

Two graphs A and B on 9 vertices, where
A has 8 edges and diameter 2, B has 10 edges and diameter 4,
and both have spectral radius r = 2*sqrt(2) (a root of x^2 - 8):
A = Graph({0: [8], 1: [8], 2: [8], 3: [8], 4: [8], 5: [8], 6: [8], 7: [8]})
B = Graph({0: [7, 8], 1: [7, 8], 2: [7, 8], 3: [7], 4: [7], 5: [8], 6: [8]})

Two graphs A and B on 10 vertices, where
A has 11 edges and diameter 3, B has 12 edges and diameter 4,
and both have spectral radius r = 3 (a root of x - 3):
A = Graph({0: [7, 8], 1: [8, 9], 2: [8], 3: [9], 4: [9], 5: [9], 6: [9], 7: [8], 8: [9]})
B = Graph({0: [7, 8], 1: [8, 9], 2: [8, 9], 3: [8, 9], 4: [9], 5: [9], 6: [9], 7: [8]})

etc.