Ask Your Question
3

Pairs of graphs with same spectral radius but with different diameter and different number of edges

asked 2018-04-12 07:47:21 +0100

Deepak Sarma gravatar image

I know that graphs.cospectral_graphs() gives all pairs of graphs with same eigenvalues. But I need graphs with same spectral radius i.e. largest eigenvalue (the other eigenvalues may be different) and differing in diameter and number of edges. What to do for this? Thank you in advance.

edit retag flag offensive close merge delete

2 Answers

Sort by ยป oldest newest most voted
1

answered 2018-04-15 18:29:30 +0100

tmonteil gravatar image

updated 2018-04-21 15:13:40 +0100

Here is a quick and dirty no-brain method:

First, we can iterate over all connected graphs of a given size up to isomorphism, see:

sage: graphs.nauty_geng?

Regarding the spectral radius, note that the spectral radius method is numerical, so there will be some noise preventing us to detect graphs with the same eigenvalue. So, we will use the largest eigenvalue of the adjacency matrix, wich is an exact algebraic number:

sage: G = graphs.RandomGNP(10,1/2)
sage: G.spectral_radius()
(4.885867917434971, 4.885867917912396)
sage: max(G.adjacency_matrix().eigenvalues())
4.885867917602611?

So, let us pick a not-so-small class of connected graphs, say graphs with 8 vertices. And let us classify each of them according to their spectral radius : we make a (lazy) dictionary that maps each spectral radius to the list of graphs with that spectral radius:

sage: from collections import defaultdict
sage: d = defaultdict(list
sage: for G in graphs.nauty_geng('8c'):
....:     d[max(G.adjacency_matrix().eigenvalues())] += [G]

We can see that there are 10350 possible eigenvalues:

sage: len(d)
10350

So let us restrict to the eigenvalues with more than one corresponding graph:

sage: dd = {i:d[i] for i in d if len(d[i])>1}
sage: len(dd)
1147

Nicer. Just to get an insight, let us look at the maximal classes:

sage: max(len(dd[i]) for i in dd)
23
sage: ddd = {i:d[i] for i in d if len(d[i])==23}
sage: len(ddd)
1

So, there is exactly one eigenvalue for which there are 23 graphs with that spectral radius. Let us inspect it further:

The eigenvalue is:

sage: e = next(iter(ddd)) ; e
3.236067977499790?
sage: e.radical_expression()
sqrt(5) + 1

The corresponding list of graphs is:

sage: L = ddd[e]

Now we can see if there are good candidates:

sage: for G in L:
....:     print(G.diameter(), G.num_edges()) 
(+Infinity, 8)
(+Infinity, 10)
(+Infinity, 9)
(+Infinity, 9)
(3, 11)
(4, 11)
(+Infinity, 9)
(+Infinity, 9)
(+Infinity, 10)
(3, 12)
(+Infinity, 11)
(+Infinity, 10)
(3, 12)
(+Infinity, 11)
(3, 11)
(3, 12)
(5, 11)
(3, 12)
(3, 12)
(+Infinity, 10)
(3, 12)
(+Infinity, 11)
(4, 12)

We can see that with the same spectral radius e there are graphs on 8 vertices with diameter and number of edges (3,11) and (4,12) respectively:

sage: G1,G2 = L[4], L[-1]
sage: G1.diameter()
3
sage: G2.diameter()
4
sage: G1.num_edges()
11
sage: G2.num_edges()
12
sage: G1.spectral_radius()
(3.2360679773376506, 3.2360679776151673)
sage: G2.spectral_radius()
(3.236067977288281, 3.2360679776071106)

Here are the pictures of the candidates:

G1

G2

We are lucky ! If no such example were found, we would have to inspect all elements of dd.

EDIT Actualy i did a typo in the use of graphs.nauty_geng('8c'), which explains why we got disconnected graphs (infinite diameter). The correct syntax is graphs.nauty_geng('8 -c'). Instead we get 9820 different spectral radius, 926 spectral radius with at least two graphs, the spectral radius with the largest number of graphs is 1/2*sqrt(17) + 3/2, and there are 12 such graphs. In that list, the pairs (diameter, num_edges) is (3,12), (4,12), (3,13), (4,13), (2,14), (3,14).

EDIT As requested in the commenrs, here is an automatic way do the whole search using a function:

def search(n=3):
    r"""
    Search, among connected graphs of size n, two graphs with the same spectral
    radius but different diameter and number of edges.
    """
    from collections import defaultdict
    d = defaultdict(list)
    for G in graphs.nauty_geng('{} -c'.format(n)):
        d[max(G.adjacency_matrix().eigenvalues())] += [G]
    for s in d:
        if len(d[s]) > 1:
            for g1 in d[s]:
                for g2 in d[s]:
                    if g1.diameter() != g2.diameter() and g1.num_edges() != g2.num_edges():
                        return (g1, g2)
    return

You can see that there are no candidates of size 5:

sage: f = search(5)
sage: f

But there are candidates of size 6:

sage: f = search(6)
sage: f
(Graph on 6 vertices, Graph on 6 vertices)
sage: g0, g1 = f
sage: g0.diameter()
3
sage: g1.diameter()
2
sage: g0.num_edges()
7
sage: g1.num_edges()
8
sage: g0.spectral_radius()
(2.7912878473346825, 2.791287847569842)
sage: g1.spectral_radius()
(2.791287847405329, 2.7912878475910357)
sage: g0.plot()
Launched png viewer for Graphics object consisting of 14 graphics primitives
sage: g1.plot()
Launched png viewer for Graphics object consisting of 15 graphics primitives

g0

g1

edit flag offensive delete link more

Comments

Thank you for the detail explanation. But what I see here we will get the graphs with same spectral radius and then we have check ourselves for graphs with different diameter and no of edges. But what to do if I want to write the program in such a way that it checks everything itself and finally give me a pair (or all such pairs) of my requirement?

Deepak Sarma gravatar imageDeepak Sarma ( 2018-04-17 05:46:54 +0100 )edit
0

answered 2019-06-10 13:46:41 +0100

slelievre gravatar image

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.

edit flag offensive delete link more

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

Stats

Asked: 2018-04-12 07:47:21 +0100

Seen: 615 times

Last updated: Jun 10 '19