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

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.

Comments

Please somebody help

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

add a comment

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

Max Alekseyev

6488 ●9 ●47 ●153

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

find_graphs(8)

It finds 3 such graphs of size 8.

edit flag offensive delete 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 ( 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 ( 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 ( 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 ( 2021-10-06 22:14:09 +0100 )edit

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 $n$ vertices (a graph on $n$ vertices is unicyclic, if it has $n$ edges). edit

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