# Consider the class of simple, connected unicyclic graphs on $n$ vertices (a graph on $n$ vertices is unicyclic, if it has $n$ edges). Anonymous

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

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?

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:


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

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