# 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.

edit retag close merge delete

( 2021-10-02 19:55:14 +0200 )edit

Sort by » oldest newest most voted

Something 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()
if f == h:
g.show()

find_graphs(8)

It finds 3 such graphs of size 8.

more

Thank 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?

( 2021-10-05 05:52:05 +0200 )edit

Yes - 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:
( 2021-10-05 15:08:25 +0200 )edit

Thank you...Can we extend this code to any connected graph? That is, not only for unicyclic graphs

( 2021-10-06 17:29:32 +0200 )edit

To remove restriction on the number of edges use for g in graphs.nauty_geng(options=f'-c {n}'):

( 2021-10-06 22:14:09 +0200 )edit

perfect....!!thank you so much

( 2021-10-07 19:20:29 +0200 )edit