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

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.

answered 3 years ago

Max Alekseyev

6932 ●9 ●52 ●162

updated 3 years ago

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:
      g.show()

find_graphs(8)

It finds 3 such graphs of size 8.

link

Comments

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 ( 3 years ago )

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 ( 3 years ago )

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

rewi ( 3 years ago )

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

Max Alekseyev ( 3 years ago )

add a comment

Your Answer

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

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

Comments

1 Answer

Comments

Your Answer

Question Tools

Stats

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

Comments

1 Answer

Comments

Your Answer

Question Tools

Stats

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