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.Sun, 27 Dec 2020 00:45:40 +0100Consider the class of all possible connected simple graphs on $n$ verticeshttps://ask.sagemath.org/question/54927/consider-the-class-of-all-possible-connected-simple-graphs-on-n-vertices/Consider the class of all possible connected simple graphs on $n$ vertices ($n$ is any natural number, we can choose any natural number). Now from this collection, can we find those graphs (if there exists any) satisfying the following property: Suppose that $A$ denotes the usual $(0,1)$ adjacency matrix of a graph. Now can we find those graphs explicitly (if there is any) on $n$ vertices such that if $\lambda$ is an eigenvalue of $A$, then $\dfrac{1}{\lambda}$ is also an eigenvalue and if $\alpha$ is another eigenvalue (distinct from $\lambda$), then $-\dfrac{1}{\alpha}$ is an eigenvalue. Basically eigenvalues of $A$ are of the form $(\lambda,\dfrac{1}{\lambda})$ and $(\alpha,-\dfrac{1}{\alpha})$.
Basically I am trying to find the graphs for which some roots of the form $(\lambda,\dfrac{1}{\lambda})$, and some roots of the form $(\alpha,-\dfrac{1}{\alpha})$.
please help regarding this problemSat, 26 Dec 2020 16:57:22 +0100https://ask.sagemath.org/question/54927/consider-the-class-of-all-possible-connected-simple-graphs-on-n-vertices/Comment by slelievre for <p>Consider the class of all possible connected simple graphs on $n$ vertices ($n$ is any natural number, we can choose any natural number). Now from this collection, can we find those graphs (if there exists any) satisfying the following property: Suppose that $A$ denotes the usual $(0,1)$ adjacency matrix of a graph. Now can we find those graphs explicitly (if there is any) on $n$ vertices such that if $\lambda$ is an eigenvalue of $A$, then $\dfrac{1}{\lambda}$ is also an eigenvalue and if $\alpha$ is another eigenvalue (distinct from $\lambda$), then $-\dfrac{1}{\alpha}$ is an eigenvalue. Basically eigenvalues of $A$ are of the form $(\lambda,\dfrac{1}{\lambda})$ and $(\alpha,-\dfrac{1}{\alpha})$.</p>
<p>Basically I am trying to find the graphs for which some roots of the form $(\lambda,\dfrac{1}{\lambda})$, and some roots of the form $(\alpha,-\dfrac{1}{\alpha})$.</p>
<p>please help regarding this problem</p>
https://ask.sagemath.org/question/54927/consider-the-class-of-all-possible-connected-simple-graphs-on-n-vertices/?comment=54938#post-id-54938This seems very related to [Ask Sage question 54878](https://ask.sagemath.org/question/54878).
The condition is now relaxed from "for any eigenvalue, both its inverse and the opposite of its inverse are also eigenvalues" to "for any eigenvalue, either its inverse or the opposite of its inverse is also an eigenvalue". Is that right?Sun, 27 Dec 2020 00:31:18 +0100https://ask.sagemath.org/question/54927/consider-the-class-of-all-possible-connected-simple-graphs-on-n-vertices/?comment=54938#post-id-54938Answer by slelievre for <p>Consider the class of all possible connected simple graphs on $n$ vertices ($n$ is any natural number, we can choose any natural number). Now from this collection, can we find those graphs (if there exists any) satisfying the following property: Suppose that $A$ denotes the usual $(0,1)$ adjacency matrix of a graph. Now can we find those graphs explicitly (if there is any) on $n$ vertices such that if $\lambda$ is an eigenvalue of $A$, then $\dfrac{1}{\lambda}$ is also an eigenvalue and if $\alpha$ is another eigenvalue (distinct from $\lambda$), then $-\dfrac{1}{\alpha}$ is an eigenvalue. Basically eigenvalues of $A$ are of the form $(\lambda,\dfrac{1}{\lambda})$ and $(\alpha,-\dfrac{1}{\alpha})$.</p>
<p>Basically I am trying to find the graphs for which some roots of the form $(\lambda,\dfrac{1}{\lambda})$, and some roots of the form $(\alpha,-\dfrac{1}{\alpha})$.</p>
<p>please help regarding this problem</p>
https://ask.sagemath.org/question/54927/consider-the-class-of-all-possible-connected-simple-graphs-on-n-vertices/?answer=54939#post-id-54939We adapt the method provided in an answer to
[Ask Sage question 54878](https://ask.sagemath.org/question/54878)
and define a function that provides an iterator over
graphs on `n` vertices with the requested property.
We then treat the case of n = 6 as an example,
and plot all the corresponding graphs.
Function:
def mygraphs(n):
return (g for g in graphs.nauty_geng(f"{n} -c")
if all(e and (1/e in ee or -1/e in ee)
for ee in [g.adjacency_matrix().eigenvalues()]
for e in ee))
List of graphs on 6 vertices with the requested property
sage: G6 = list(mygraphs(6))
sage: len(G6)
6
View them:
sage: opt = {'axes': False, 'aspect_ratio': 1, 'color': 'grey', 'alpha': 0}
sage: p = point2d([(-1.2, -1.2), (1.2, 1.2)], **opt)
sage: gg = [p + g.plot(layout='circular') for g in G6]
sage: graphics_array(gg, ncols=3)
![Graphs on 6 vertices with eigenvalue condition](/upfiles/16090264898172497.png)Sun, 27 Dec 2020 00:45:40 +0100https://ask.sagemath.org/question/54927/consider-the-class-of-all-possible-connected-simple-graphs-on-n-vertices/?answer=54939#post-id-54939