Ask Your Question
1

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

asked 2021-12-15 16:32:05 +0100

anonymous user

Anonymous

updated 2021-12-15 16:39:32 +0100

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$C:\fakepath\t56.PNG

edit retag flag offensive close merge delete

Comments

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

Max Alekseyev gravatar imageMax Alekseyev ( 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?

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

1 Answer

Sort by ยป oldest newest most voted
1

answered 2021-12-15 18:56:28 +0100

Max Alekseyev gravatar image

updated 2021-12-16 15:05:34 +0100

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
        S.add( G.canonical_label(edge_labels=True).copy(weighted=True,immutable=True) )
        # 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:

image description


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

for H in get_graphs(6):
    A = H.weighted_adjacency_matrix()
    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]})
    h /= h.leading_coefficient()
    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]
edit flag offensive delete link more

Comments

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

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

Yes - here is an example:

for H in get_graphs(4):
    A = H.weighted_adjacency_matrix()
    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')
Max Alekseyev gravatar imageMax Alekseyev ( 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.

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

Test this:

f = A.characteristic_polynomial()
h = f.reverse().subs({f.variables()[0]:-f.variables()[0]})
h /= h.leading_coefficient()
if f==h:
    ....
Max Alekseyev gravatar imageMax Alekseyev ( 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?

rewi gravatar imagerewi ( 2021-12-16 08:43:24 +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

Stats

Asked: 2021-12-15 16:32:05 +0100

Seen: 30,762 times

Last updated: Dec 16 '21