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.Wed, 06 Oct 2021 22:14:09 +0200Consider the class of simple, connected unicyclic graphs on $n$ vertices (a graph on $n$ vertices is unicyclic, if it has $n$ edges).https://ask.sagemath.org/question/59220/consider-the-class-of-simple-connected-unicyclic-graphs-on-n-vertices-a-graph-on-n-vertices-is-unicyclic-if-it-has-n-edges/Consider the class of simple, connected unicyclic graphs on $n$ vertices (a graph on $n$ vertices is unicyclic, if it has $n$ edges). Now from this collection, consider the collection $S$ of all those graph for which the corresponding adjacency matrices are singular (i.e, having determinant is zero). Now from this collection $S$, can we find a graph that satisfies the following property: if $\lambda$ is an non zero eigenvalue of the adjacency matrix iff $\dfrac{1}{\lambda}$ is also an eigenvalue of the adjacency matrix.Fri, 01 Oct 2021 20:10:43 +0200https://ask.sagemath.org/question/59220/consider-the-class-of-simple-connected-unicyclic-graphs-on-n-vertices-a-graph-on-n-vertices-is-unicyclic-if-it-has-n-edges/Comment by rewi for <p>Consider the class of simple, connected unicyclic graphs on $n$ vertices (a graph on $n$ vertices is unicyclic, if it has $n$ edges). Now from this collection, consider the collection $S$ of all those graph for which the corresponding adjacency matrices are singular (i.e, having determinant is zero). Now from this collection $S$, can we find a graph that satisfies the following property: if $\lambda$ is an non zero eigenvalue of the adjacency matrix iff $\dfrac{1}{\lambda}$ is also an eigenvalue of the adjacency matrix.</p>
https://ask.sagemath.org/question/59220/consider-the-class-of-simple-connected-unicyclic-graphs-on-n-vertices-a-graph-on-n-vertices-is-unicyclic-if-it-has-n-edges/?comment=59226#post-id-59226Please somebody helpSat, 02 Oct 2021 19:55:14 +0200https://ask.sagemath.org/question/59220/consider-the-class-of-simple-connected-unicyclic-graphs-on-n-vertices-a-graph-on-n-vertices-is-unicyclic-if-it-has-n-edges/?comment=59226#post-id-59226Answer by Max Alekseyev for <p>Consider the class of simple, connected unicyclic graphs on $n$ vertices (a graph on $n$ vertices is unicyclic, if it has $n$ edges). Now from this collection, consider the collection $S$ of all those graph for which the corresponding adjacency matrices are singular (i.e, having determinant is zero). Now from this collection $S$, can we find a graph that satisfies the following property: if $\lambda$ is an non zero eigenvalue of the adjacency matrix iff $\dfrac{1}{\lambda}$ is also an eigenvalue of the adjacency matrix.</p>
https://ask.sagemath.org/question/59220/consider-the-class-of-simple-connected-unicyclic-graphs-on-n-vertices-a-graph-on-n-vertices-is-unicyclic-if-it-has-n-edges/?answer=59238#post-id-59238Something like this will do the job:
def find_graphs(n):
for g in graphs.nauty_geng(options=f'-c {n} {n}:{n}'):
f = g.characteristic_polynomial()
h = f.reverse()
h /= h.leading_coefficient()
if f == h:
g.show()
find_graphs(8)
It finds 3 such graphs of size 8.Mon, 04 Oct 2021 23:27:31 +0200https://ask.sagemath.org/question/59220/consider-the-class-of-simple-connected-unicyclic-graphs-on-n-vertices-a-graph-on-n-vertices-is-unicyclic-if-it-has-n-edges/?answer=59238#post-id-59238Comment by Max Alekseyev for <p>Something like this will do the job:</p>
<pre><code>def find_graphs(n):
for g in graphs.nauty_geng(options=f'-c {n} {n}:{n}'):
f = g.characteristic_polynomial()
h = f.reverse()
h /= h.leading_coefficient()
if f == h:
g.show()
find_graphs(8)
</code></pre>
<p>It finds 3 such graphs of size 8.</p>
https://ask.sagemath.org/question/59220/consider-the-class-of-simple-connected-unicyclic-graphs-on-n-vertices-a-graph-on-n-vertices-is-unicyclic-if-it-has-n-edges/?comment=59255#post-id-59255To remove restriction on the number of edges use `for g in graphs.nauty_geng(options=f'-c {n}'):`Wed, 06 Oct 2021 22:14:09 +0200https://ask.sagemath.org/question/59220/consider-the-class-of-simple-connected-unicyclic-graphs-on-n-vertices-a-graph-on-n-vertices-is-unicyclic-if-it-has-n-edges/?comment=59255#post-id-59255Comment by rewi for <p>Something like this will do the job:</p>
<pre><code>def find_graphs(n):
for g in graphs.nauty_geng(options=f'-c {n} {n}:{n}'):
f = g.characteristic_polynomial()
h = f.reverse()
h /= h.leading_coefficient()
if f == h:
g.show()
find_graphs(8)
</code></pre>
<p>It finds 3 such graphs of size 8.</p>
https://ask.sagemath.org/question/59220/consider-the-class-of-simple-connected-unicyclic-graphs-on-n-vertices-a-graph-on-n-vertices-is-unicyclic-if-it-has-n-edges/?comment=59251#post-id-59251Thank you...Can we extend this code to any connected graph? That is, not only for unicyclic graphsWed, 06 Oct 2021 17:29:32 +0200https://ask.sagemath.org/question/59220/consider-the-class-of-simple-connected-unicyclic-graphs-on-n-vertices-a-graph-on-n-vertices-is-unicyclic-if-it-has-n-edges/?comment=59251#post-id-59251Comment by Max Alekseyev for <p>Something like this will do the job:</p>
<pre><code>def find_graphs(n):
for g in graphs.nauty_geng(options=f'-c {n} {n}:{n}'):
f = g.characteristic_polynomial()
h = f.reverse()
h /= h.leading_coefficient()
if f == h:
g.show()
find_graphs(8)
</code></pre>
<p>It finds 3 such graphs of size 8.</p>
https://ask.sagemath.org/question/59220/consider-the-class-of-simple-connected-unicyclic-graphs-on-n-vertices-a-graph-on-n-vertices-is-unicyclic-if-it-has-n-edges/?comment=59241#post-id-59241Yes - restricting to singular adjacency matrices and nonzero eigenvalues can be achieved by changing the `if f == h:` condition to
if f.ord()>0 and f.shift(-f.ord()) == h:Tue, 05 Oct 2021 15:08:25 +0200https://ask.sagemath.org/question/59220/consider-the-class-of-simple-connected-unicyclic-graphs-on-n-vertices-a-graph-on-n-vertices-is-unicyclic-if-it-has-n-edges/?comment=59241#post-id-59241Comment by rewi for <p>Something like this will do the job:</p>
<pre><code>def find_graphs(n):
for g in graphs.nauty_geng(options=f'-c {n} {n}:{n}'):
f = g.characteristic_polynomial()
h = f.reverse()
h /= h.leading_coefficient()
if f == h:
g.show()
find_graphs(8)
</code></pre>
<p>It finds 3 such graphs of size 8.</p>
https://ask.sagemath.org/question/59220/consider-the-class-of-simple-connected-unicyclic-graphs-on-n-vertices-a-graph-on-n-vertices-is-unicyclic-if-it-has-n-edges/?comment=59240#post-id-59240Thank you for the answer. But I require those graphs only whose adjacency matrices are singular and the non zero eigenvalues satisfies the stated property. All the 3 graphs, obtained by you, are having non singular adjacecy matrices. I actually need the adjecency matrices should be singular while the corresponding non zero eigenvalues of the adjacency matrices satisfies the stated property above. Can we do this?Tue, 05 Oct 2021 05:52:05 +0200https://ask.sagemath.org/question/59220/consider-the-class-of-simple-connected-unicyclic-graphs-on-n-vertices-a-graph-on-n-vertices-is-unicyclic-if-it-has-n-edges/?comment=59240#post-id-59240