# How to construct the class of all connected weighted unicyclic graphs on $n$ vertices, where exactly one edge of the cycle in the unicyclic graphs

How to construct the class of all connected weighted unicyclic graphs (a connected graph on $n$ vertices is said to be unicyclic if it has $n$ edges) on $n$ vertices, where exactly one edge of the cycle in the unicyclic graphs has weight $i\,(=\sqrt{-1})$ and remaining all the edges in the graphs are of weight $1$ For example consider the following graph together with its adjacency matrix. In the adjacency matrix we take the entry (3,4) as $i$ and $(4,3)$ as $-i$, that is, just the conjugate of $i$

edit retag close merge delete

You show graph as undirected, but its adjacency matrix is not symmetric. Please clarify.

( 2021-12-15 17:03:39 +0100 )edit

ok. actualy the graph has only one edge of weight $i$. Suppose that $[i,j]$ be the edge of weight $i$. then direction is anything, that is, one can take from i to j or from j to i. if direction is from i to j then (i,j)th entry of adjacency matrix will be $i$, and (j,i) entry is $-i$. In this case adjacency matrix will be Hermitian matrix. In the whole graph $[i,j]$ is the directed edge all other esges are non directed.

Am I clear now?

( 2021-12-15 17:13:17 +0100 )edit

Sort by » oldest newest most voted

The problem can be approached with the following steps:

1. Use nauty to generate all connected unicyclic graphs on $n$ vertices, like in my earlier answer. In each such graph:
1. assign weight 1 to all edges
2. find its unique cycle and iteratively assign weight $i$ to each of its edges
3. use canonical labeling to eliminate duplicates

Here is a sample code:

def get_graphs(n):
S = set()
# iterate over all connected unicyclic graphs with n vertices
for G in graphs.nauty_geng(options=f'-c {n} {n}:{n}'):
# assign weight 1 to all edges of G
for e in G.edges(labels=False):
G.set_edge_label(e[0], e[1], 1)
# set of edges participating in cycles
E = set.union( *(set(c) for c in G.cycle_basis(output='edge')) )
for e in E:
# temporarily set weight of e to I
G.set_edge_label(e[0], e[1], I)
# add canonical labeling of G to set S
# restore weight of e to 1
G.set_edge_label(e[0], e[1], 1)
return S


For example,

for H in get_graphs(4): H.show(edge_labels=True)


produces 3 graphs:

ADDED. This is how we get matrices requested in the comments (for $n=6$ as an example):

for H in get_graphs(6):
p = [(i,j) for i in range(A.nrows()) for j in range(i) if A[i,j]==I][0]
A[p] = -I
f = A.characteristic_polynomial()
h = f.reverse().subs({f.variables()[0]:-f.variables()[0]})
if f==h:
print(A,end='\n\n')


It prints the following 3 matrices:

[ 0  0  0  1  0  0]
[ 0  0  0  0  0  1]
[ 0  0  0  0  1  I]
[ 1  0  0  0  0  1]
[ 0  0  1  0  0  1]
[ 0  1 -I  1  1  0]

[ 0  0  0  0  1  0]
[ 0  0  0  1  0  0]
[ 0  0  0  0  0  1]
[ 0  1  0  0  I  1]
[ 1  0  0 -I  0  1]
[ 0  0  1  1  1  0]

[ 0  0  0  0  0  1]
[ 0  0  0  0  1  0]
[ 0  0  0  I  0  1]
[ 0  0 -I  0  0  1]
[ 0  1  0  0  0  1]
[ 1  0  1  1  1  0]

more

Nice answer. Can I also obtain the corresponding adjacency matrices of these graphs?

( 2021-12-15 19:15:36 +0100 )edit

Yes - here is an example:

for H in get_graphs(4):
p = [(i,j) for i in range(A.nrows()) for j in range(i) if A[i,j]==I][0]
A[p] = -I
print(A,end='\n\n')

( 2021-12-15 19:31:28 +0100 )edit

Ok. Thanks. Now from this collection , can we find those graphs that satisfies the following property: if $\lambda$ is an non zero eigenvalue of the adjacency matrix iff $-1/\lambda$ is also an eigenvalue of the adjacency matrix.

( 2021-12-15 19:50:35 +0100 )edit

Test this:

f = A.characteristic_polynomial()
h = f.reverse().subs({f.variables()[0]:-f.variables()[0]})
if f==h:
....

( 2021-12-15 22:17:15 +0100 )edit

Ok. I compile the code but there is some error. If possible, can you please give the whole code together?

( 2021-12-16 08:43:24 +0100 )edit