ASKSAGE: Sage Q&A Forum - RSS feedhttps://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Mon, 10 Jun 2019 13:46:41 +0200Pairs of graphs with same spectral radius but with different diameter and different number of edgeshttps://ask.sagemath.org/question/41990/pairs-of-graphs-with-same-spectral-radius-but-with-different-diameter-and-different-number-of-edges/ 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.Thu, 12 Apr 2018 07:47:21 +0200https://ask.sagemath.org/question/41990/pairs-of-graphs-with-same-spectral-radius-but-with-different-diameter-and-different-number-of-edges/Answer by slelievre for <p>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.</p>
https://ask.sagemath.org/question/41990/pairs-of-graphs-with-same-spectral-radius-but-with-different-diameter-and-different-number-of-edges/?answer=46895#post-id-46895If 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.Mon, 10 Jun 2019 13:46:41 +0200https://ask.sagemath.org/question/41990/pairs-of-graphs-with-same-spectral-radius-but-with-different-diameter-and-different-number-of-edges/?answer=46895#post-id-46895Answer by tmonteil for <p>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.</p>
https://ask.sagemath.org/question/41990/pairs-of-graphs-with-same-spectral-radius-but-with-different-diameter-and-different-number-of-edges/?answer=42014#post-id-42014Here 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](/upfiles/1523809834868125.png)
![G2](/upfiles/15238098595911069.png)
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](/upfiles/15243163893447771.png)
![g1](/upfiles/15243164059263362.png)
Sun, 15 Apr 2018 18:29:30 +0200https://ask.sagemath.org/question/41990/pairs-of-graphs-with-same-spectral-radius-but-with-different-diameter-and-different-number-of-edges/?answer=42014#post-id-42014Comment by Deepak Sarma for <p>Here is a quick and dirty no-brain method:</p>
<p>First, we can iterate over all connected graphs of a given size up to isomorphism, see:</p>
<pre><code>sage: graphs.nauty_geng?
</code></pre>
<p>Regarding the spectral radius, note that the <code>spectral radius</code> 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:</p>
<pre><code>sage: G = graphs.RandomGNP(10,1/2)
sage: G.spectral_radius()
(4.885867917434971, 4.885867917912396)
sage: max(G.adjacency_matrix().eigenvalues())
4.885867917602611?
</code></pre>
<p>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:</p>
<pre><code>sage: from collections import defaultdict
sage: d = defaultdict(list
sage: for G in graphs.nauty_geng('8c'):
....: d[max(G.adjacency_matrix().eigenvalues())] += [G]
</code></pre>
<p>We can see that there are 10350 possible eigenvalues: </p>
<pre><code>sage: len(d)
10350
</code></pre>
<p>So let us restrict to the eigenvalues with more than one corresponding graph:</p>
<pre><code>sage: dd = {i:d[i] for i in d if len(d[i])>1}
sage: len(dd)
1147
</code></pre>
<p>Nicer. Just to get an insight, let us look at the maximal classes:</p>
<pre><code>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
</code></pre>
<p>So, there is exactly one eigenvalue for which there are 23 graphs with that spectral radius. Let us inspect it further:</p>
<p>The eigenvalue is:</p>
<pre><code>sage: e = next(iter(ddd)) ; e
3.236067977499790?
sage: e.radical_expression()
sqrt(5) + 1
</code></pre>
<p>The corresponding list of graphs is:</p>
<pre><code>sage: L = ddd[e]
</code></pre>
<p>Now we can see if there are good candidates:</p>
<pre><code>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)
</code></pre>
<p>We can see that with the same spectral radius <code>e</code> there are graphs on 8 vertices with diameter and number of edges <code>(3,11)</code> and <code>(4,12)</code> respectively:</p>
<pre><code>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)
</code></pre>
<p>Here are the pictures of the candidates:</p>
<p><img alt="G1" src="/upfiles/1523809834868125.png"></p>
<p><img alt="G2" src="/upfiles/15238098595911069.png"></p>
<p>We are lucky ! If no such example were found, we would have to inspect all elements of <code>dd</code>.</p>
<p><strong>EDIT</strong> Actualy i did a typo in the use of <code>graphs.nauty_geng('8c')</code>, which explains why we got disconnected graphs (infinite diameter). The correct syntax is <code>graphs.nauty_geng('8 -c')</code>. 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 <code>1/2*sqrt(17) + 3/2</code>, and there are 12 such graphs. In that list, the pairs (diameter, num_edges) is <code>(3,12), (4,12), (3,13), (4,13), (2,14), (3,14)</code>.</p>
<p><strong>EDIT</strong> As requested in the commenrs, here is an automatic way do the whole search using a function:</p>
<pre><code>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
</code></pre>
<p>You can see that there are no candidates of size 5:</p>
<pre><code>sage: f = search(5)
sage: f
</code></pre>
<p>But there are candidates of size 6:</p>
<pre><code>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
</code></pre>
<p><img alt="g0" src="/upfiles/15243163893447771.png"></p>
<p><img alt="g1" src="/upfiles/15243164059263362.png"></p>
https://ask.sagemath.org/question/41990/pairs-of-graphs-with-same-spectral-radius-but-with-different-diameter-and-different-number-of-edges/?comment=42054#post-id-42054Thank 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?Tue, 17 Apr 2018 05:46:54 +0200https://ask.sagemath.org/question/41990/pairs-of-graphs-with-same-spectral-radius-but-with-different-diameter-and-different-number-of-edges/?comment=42054#post-id-42054