ASKSAGE: Sage Q&A Forum - RSS feedhttps://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Thu, 16 Dec 2021 16:11:45 +0100How to construct the class of all connected weighted unicyclic graphs on $n$ vertices, where exactly one edge of the cycle in the unicyclic graphshttps://ask.sagemath.org/question/60280/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$![C:\fakepath\t56.PNG](/upfiles/1639582539546511.png)Wed, 15 Dec 2021 16:32:05 +0100https://ask.sagemath.org/question/60280/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/Comment by rewi for <p>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$<img src="/upfiles/1639582539546511.png" alt="C:\fakepath\t56.PNG"></p>
https://ask.sagemath.org/question/60280/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/?comment=60292#post-id-60292ok. 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?Wed, 15 Dec 2021 17:13:17 +0100https://ask.sagemath.org/question/60280/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/?comment=60292#post-id-60292Comment by Max Alekseyev for <p>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$<img src="/upfiles/1639582539546511.png" alt="C:\fakepath\t56.PNG"></p>
https://ask.sagemath.org/question/60280/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/?comment=60290#post-id-60290You show graph as undirected, but its adjacency matrix is not symmetric. Please clarify.Wed, 15 Dec 2021 17:03:39 +0100https://ask.sagemath.org/question/60280/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/?comment=60290#post-id-60290Answer by Max Alekseyev for <p>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$<img src="/upfiles/1639582539546511.png" alt="C:\fakepath\t56.PNG"></p>
https://ask.sagemath.org/question/60280/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/?answer=60298#post-id-60298The 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](https://ask.sagemath.org/question/59220/consider-the-class-of-simple-connected-unicyclic-graphs-on-n-vertices-a-graph-on-n-vertices-is-unicyclic-if-it-has-n-edges/?answer=59238#post-id-59238). 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](/upfiles/16395909526627102.png)
---
**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]Wed, 15 Dec 2021 18:56:28 +0100https://ask.sagemath.org/question/60280/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/?answer=60298#post-id-60298Comment by rewi for <p>The problem can be approached with the following steps:</p>
<ol>
<li>Use nauty to generate all connected unicyclic graphs on $n$ vertices, like in my <a href="https://ask.sagemath.org/question/59220/consider-the-class-of-simple-connected-unicyclic-graphs-on-n-vertices-a-graph-on-n-vertices-is-unicyclic-if-it-has-n-edges/?answer=59238#post-id-59238">earlier answer</a>. In each such graph:
<ol>
<li>assign weight 1 to all edges</li>
<li>find its unique cycle and iteratively assign weight $i$ to each of its edges</li>
<li>use canonical labeling to eliminate duplicates</li>
</ol></li>
</ol>
<p>Here is a sample code:</p>
<pre><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
</code></pre>
<p>For example, </p>
<pre><code>for H in get_graphs(4): H.show(edge_labels=True)
</code></pre>
<p>produces 3 graphs:</p>
<p><img src="/upfiles/16395909526627102.png" alt="image description"></p>
<hr>
<p><strong>ADDED.</strong> This is how we get matrices requested in the comments (for $n=6$ as an example):</p>
<pre><code>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')
</code></pre>
<p>It prints the following 3 matrices:</p>
<pre><code>[ 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]
</code></pre>
https://ask.sagemath.org/question/60280/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/?comment=60314#post-id-60314Thank you so much.Thu, 16 Dec 2021 16:11:45 +0100https://ask.sagemath.org/question/60280/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/?comment=60314#post-id-60314Comment by Max Alekseyev for <p>The problem can be approached with the following steps:</p>
<ol>
<li>Use nauty to generate all connected unicyclic graphs on $n$ vertices, like in my <a href="https://ask.sagemath.org/question/59220/consider-the-class-of-simple-connected-unicyclic-graphs-on-n-vertices-a-graph-on-n-vertices-is-unicyclic-if-it-has-n-edges/?answer=59238#post-id-59238">earlier answer</a>. In each such graph:
<ol>
<li>assign weight 1 to all edges</li>
<li>find its unique cycle and iteratively assign weight $i$ to each of its edges</li>
<li>use canonical labeling to eliminate duplicates</li>
</ol></li>
</ol>
<p>Here is a sample code:</p>
<pre><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
</code></pre>
<p>For example, </p>
<pre><code>for H in get_graphs(4): H.show(edge_labels=True)
</code></pre>
<p>produces 3 graphs:</p>
<p><img src="/upfiles/16395909526627102.png" alt="image description"></p>
<hr>
<p><strong>ADDED.</strong> This is how we get matrices requested in the comments (for $n=6$ as an example):</p>
<pre><code>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')
</code></pre>
<p>It prints the following 3 matrices:</p>
<pre><code>[ 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]
</code></pre>
https://ask.sagemath.org/question/60280/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/?comment=60312#post-id-60312I've added the code.Thu, 16 Dec 2021 15:06:03 +0100https://ask.sagemath.org/question/60280/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/?comment=60312#post-id-60312Comment by rewi for <p>The problem can be approached with the following steps:</p>
<ol>
<li>Use nauty to generate all connected unicyclic graphs on $n$ vertices, like in my <a href="https://ask.sagemath.org/question/59220/consider-the-class-of-simple-connected-unicyclic-graphs-on-n-vertices-a-graph-on-n-vertices-is-unicyclic-if-it-has-n-edges/?answer=59238#post-id-59238">earlier answer</a>. In each such graph:
<ol>
<li>assign weight 1 to all edges</li>
<li>find its unique cycle and iteratively assign weight $i$ to each of its edges</li>
<li>use canonical labeling to eliminate duplicates</li>
</ol></li>
</ol>
<p>Here is a sample code:</p>
<pre><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
</code></pre>
<p>For example, </p>
<pre><code>for H in get_graphs(4): H.show(edge_labels=True)
</code></pre>
<p>produces 3 graphs:</p>
<p><img src="/upfiles/16395909526627102.png" alt="image description"></p>
<hr>
<p><strong>ADDED.</strong> This is how we get matrices requested in the comments (for $n=6$ as an example):</p>
<pre><code>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')
</code></pre>
<p>It prints the following 3 matrices:</p>
<pre><code>[ 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]
</code></pre>
https://ask.sagemath.org/question/60280/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/?comment=60308#post-id-60308I compiled the following 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 H in get_graphs(6):
A = H.weighted_adjacency_matrix()Thu, 16 Dec 2021 08:46:07 +0100https://ask.sagemath.org/question/60280/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/?comment=60308#post-id-60308Comment by rewi for <p>The problem can be approached with the following steps:</p>
<ol>
<li>Use nauty to generate all connected unicyclic graphs on $n$ vertices, like in my <a href="https://ask.sagemath.org/question/59220/consider-the-class-of-simple-connected-unicyclic-graphs-on-n-vertices-a-graph-on-n-vertices-is-unicyclic-if-it-has-n-edges/?answer=59238#post-id-59238">earlier answer</a>. In each such graph:
<ol>
<li>assign weight 1 to all edges</li>
<li>find its unique cycle and iteratively assign weight $i$ to each of its edges</li>
<li>use canonical labeling to eliminate duplicates</li>
</ol></li>
</ol>
<p>Here is a sample code:</p>
<pre><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
</code></pre>
<p>For example, </p>
<pre><code>for H in get_graphs(4): H.show(edge_labels=True)
</code></pre>
<p>produces 3 graphs:</p>
<p><img src="/upfiles/16395909526627102.png" alt="image description"></p>
<hr>
<p><strong>ADDED.</strong> This is how we get matrices requested in the comments (for $n=6$ as an example):</p>
<pre><code>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')
</code></pre>
<p>It prints the following 3 matrices:</p>
<pre><code>[ 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]
</code></pre>
https://ask.sagemath.org/question/60280/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/?comment=60307#post-id-60307Ok. I compile the code but there is some error. If possible, can you please give the whole code together?Thu, 16 Dec 2021 08:43:24 +0100https://ask.sagemath.org/question/60280/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/?comment=60307#post-id-60307Comment by Max Alekseyev for <p>The problem can be approached with the following steps:</p>
<ol>
<li>Use nauty to generate all connected unicyclic graphs on $n$ vertices, like in my <a href="https://ask.sagemath.org/question/59220/consider-the-class-of-simple-connected-unicyclic-graphs-on-n-vertices-a-graph-on-n-vertices-is-unicyclic-if-it-has-n-edges/?answer=59238#post-id-59238">earlier answer</a>. In each such graph:
<ol>
<li>assign weight 1 to all edges</li>
<li>find its unique cycle and iteratively assign weight $i$ to each of its edges</li>
<li>use canonical labeling to eliminate duplicates</li>
</ol></li>
</ol>
<p>Here is a sample code:</p>
<pre><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
</code></pre>
<p>For example, </p>
<pre><code>for H in get_graphs(4): H.show(edge_labels=True)
</code></pre>
<p>produces 3 graphs:</p>
<p><img src="/upfiles/16395909526627102.png" alt="image description"></p>
<hr>
<p><strong>ADDED.</strong> This is how we get matrices requested in the comments (for $n=6$ as an example):</p>
<pre><code>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')
</code></pre>
<p>It prints the following 3 matrices:</p>
<pre><code>[ 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]
</code></pre>
https://ask.sagemath.org/question/60280/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/?comment=60303#post-id-60303Test this:
f = A.characteristic_polynomial()
h = f.reverse().subs({f.variables()[0]:-f.variables()[0]})
h /= h.leading_coefficient()
if f==h:
....Wed, 15 Dec 2021 22:17:15 +0100https://ask.sagemath.org/question/60280/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/?comment=60303#post-id-60303Comment by rewi for <p>The problem can be approached with the following steps:</p>
<ol>
<li>Use nauty to generate all connected unicyclic graphs on $n$ vertices, like in my <a href="https://ask.sagemath.org/question/59220/consider-the-class-of-simple-connected-unicyclic-graphs-on-n-vertices-a-graph-on-n-vertices-is-unicyclic-if-it-has-n-edges/?answer=59238#post-id-59238">earlier answer</a>. In each such graph:
<ol>
<li>assign weight 1 to all edges</li>
<li>find its unique cycle and iteratively assign weight $i$ to each of its edges</li>
<li>use canonical labeling to eliminate duplicates</li>
</ol></li>
</ol>
<p>Here is a sample code:</p>
<pre><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
</code></pre>
<p>For example, </p>
<pre><code>for H in get_graphs(4): H.show(edge_labels=True)
</code></pre>
<p>produces 3 graphs:</p>
<p><img src="/upfiles/16395909526627102.png" alt="image description"></p>
<hr>
<p><strong>ADDED.</strong> This is how we get matrices requested in the comments (for $n=6$ as an example):</p>
<pre><code>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')
</code></pre>
<p>It prints the following 3 matrices:</p>
<pre><code>[ 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]
</code></pre>
https://ask.sagemath.org/question/60280/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/?comment=60301#post-id-60301Ok. 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.Wed, 15 Dec 2021 19:50:35 +0100https://ask.sagemath.org/question/60280/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/?comment=60301#post-id-60301Comment by Max Alekseyev for <p>The problem can be approached with the following steps:</p>
<ol>
<li>Use nauty to generate all connected unicyclic graphs on $n$ vertices, like in my <a href="https://ask.sagemath.org/question/59220/consider-the-class-of-simple-connected-unicyclic-graphs-on-n-vertices-a-graph-on-n-vertices-is-unicyclic-if-it-has-n-edges/?answer=59238#post-id-59238">earlier answer</a>. In each such graph:
<ol>
<li>assign weight 1 to all edges</li>
<li>find its unique cycle and iteratively assign weight $i$ to each of its edges</li>
<li>use canonical labeling to eliminate duplicates</li>
</ol></li>
</ol>
<p>Here is a sample code:</p>
<pre><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
</code></pre>
<p>For example, </p>
<pre><code>for H in get_graphs(4): H.show(edge_labels=True)
</code></pre>
<p>produces 3 graphs:</p>
<p><img src="/upfiles/16395909526627102.png" alt="image description"></p>
<hr>
<p><strong>ADDED.</strong> This is how we get matrices requested in the comments (for $n=6$ as an example):</p>
<pre><code>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')
</code></pre>
<p>It prints the following 3 matrices:</p>
<pre><code>[ 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]
</code></pre>
https://ask.sagemath.org/question/60280/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/?comment=60300#post-id-60300Yes - 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')Wed, 15 Dec 2021 19:31:28 +0100https://ask.sagemath.org/question/60280/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/?comment=60300#post-id-60300Comment by rewi for <p>The problem can be approached with the following steps:</p>
<ol>
<li>Use nauty to generate all connected unicyclic graphs on $n$ vertices, like in my <a href="https://ask.sagemath.org/question/59220/consider-the-class-of-simple-connected-unicyclic-graphs-on-n-vertices-a-graph-on-n-vertices-is-unicyclic-if-it-has-n-edges/?answer=59238#post-id-59238">earlier answer</a>. In each such graph:
<ol>
<li>assign weight 1 to all edges</li>
<li>find its unique cycle and iteratively assign weight $i$ to each of its edges</li>
<li>use canonical labeling to eliminate duplicates</li>
</ol></li>
</ol>
<p>Here is a sample code:</p>
<pre><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
</code></pre>
<p>For example, </p>
<pre><code>for H in get_graphs(4): H.show(edge_labels=True)
</code></pre>
<p>produces 3 graphs:</p>
<p><img src="/upfiles/16395909526627102.png" alt="image description"></p>
<hr>
<p><strong>ADDED.</strong> This is how we get matrices requested in the comments (for $n=6$ as an example):</p>
<pre><code>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')
</code></pre>
<p>It prints the following 3 matrices:</p>
<pre><code>[ 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]
</code></pre>
https://ask.sagemath.org/question/60280/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/?comment=60299#post-id-60299Nice answer. Can I also obtain the corresponding adjacency matrices of these graphs?Wed, 15 Dec 2021 19:15:36 +0100https://ask.sagemath.org/question/60280/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/?comment=60299#post-id-60299