Ask Your Question

Consider the class of all possible connected simple graphs on $n$ vertices

asked 2020-12-26 16:57:22 +0100

anonymous user


updated 2020-12-26 19:12:26 +0100

Consider the class of all possible connected simple graphs on $n$ vertices ($n$ is any natural number, we can choose any natural number). Now from this collection, can we find those graphs (if there exists any) satisfying the following property: Suppose that $A$ denotes the usual $(0,1)$ adjacency matrix of a graph. Now can we find those graphs explicitly (if there is any) on $n$ vertices such that if $\lambda$ is an eigenvalue of $A$, then $\dfrac{1}{\lambda}$ is also an eigenvalue and if $\alpha$ is another eigenvalue (distinct from $\lambda$), then $-\dfrac{1}{\alpha}$ is an eigenvalue. Basically eigenvalues of $A$ are of the form $(\lambda,\dfrac{1}{\lambda})$ and $(\alpha,-\dfrac{1}{\alpha})$.

Basically I am trying to find the graphs for which some roots of the form $(\lambda,\dfrac{1}{\lambda})$, and some roots of the form $(\alpha,-\dfrac{1}{\alpha})$.

please help regarding this problem

edit retag flag offensive close merge delete


This seems very related to Ask Sage question 54878.

The condition is now relaxed from "for any eigenvalue, both its inverse and the opposite of its inverse are also eigenvalues" to "for any eigenvalue, either its inverse or the opposite of its inverse is also an eigenvalue". Is that right?

slelievre gravatar imageslelievre ( 2020-12-27 00:31:18 +0100 )edit

1 Answer

Sort by ยป oldest newest most voted

answered 2020-12-27 00:45:40 +0100

slelievre gravatar image

updated 2020-12-27 00:49:02 +0100

We adapt the method provided in an answer to Ask Sage question 54878 and define a function that provides an iterator over graphs on n vertices with the requested property.

We then treat the case of n = 6 as an example, and plot all the corresponding graphs.


def mygraphs(n):
    return (g for g in graphs.nauty_geng(f"{n} -c")
            if all(e and (1/e in ee or -1/e in ee)
                   for ee in [g.adjacency_matrix().eigenvalues()]
                   for e in ee))

List of graphs on 6 vertices with the requested property

sage: G6 = list(mygraphs(6))
sage: len(G6)

View them:

sage: opt = {'axes': False, 'aspect_ratio': 1, 'color': 'grey', 'alpha': 0}
sage: p = point2d([(-1.2, -1.2), (1.2, 1.2)], **opt)
sage: gg = [p + g.plot(layout='circular') for g in G6]
sage: graphics_array(gg, ncols=3)

Graphs on 6 vertices with eigenvalue condition

edit flag offensive delete link more

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: 2020-12-26 16:57:22 +0100

Seen: 210 times

Last updated: Dec 27 '20