Ask Your Question

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

asked 2021-10-01 20:10:43 +0100

anonymous user


updated 2021-10-05 05:44:51 +0100

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 flag offensive close merge delete


Please somebody help

rewi gravatar imagerewi ( 2021-10-02 19:55:14 +0100 )edit

1 Answer

Sort by ยป oldest newest most voted

answered 2021-10-04 23:27:31 +0100

Max Alekseyev gravatar image

updated 2021-10-04 23:54:40 +0100

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()
    h /= h.leading_coefficient()
    if f == h:


It finds 3 such graphs of size 8.

edit flag offensive delete link 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?

rewi gravatar imagerewi ( 2021-10-05 05:52:05 +0100 )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:
Max Alekseyev gravatar imageMax Alekseyev ( 2021-10-05 15:08:25 +0100 )edit

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

rewi gravatar imagerewi ( 2021-10-06 17:29:32 +0100 )edit

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

Max Alekseyev gravatar imageMax Alekseyev ( 2021-10-06 22:14:09 +0100 )edit

perfect....!!thank you so much

rewi gravatar imagerewi ( 2021-10-07 19:20:29 +0100 )edit

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

1 follower


Asked: 2021-10-01 20:10:43 +0100

Seen: 163 times

Last updated: Oct 05 '21