Ask Your Question
1

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

asked 2018-04-12 00:47:21 -0500

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

1 answer

Sort by ยป oldest newest most voted
1

answered 2018-04-15 11:29:30 -0500

tmonteil gravatar image

updated 2018-04-21 08:13:40 -0500

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-16 22:46:54 -0500 )edit

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 00:47:21 -0500

Seen: 79 times

Last updated: Apr 21