Consider the class of simple connected bicyclic graphs on $10$ vertices. Let $A$ be the adjacency matrix of any such graph.

Consider the class of simple connected bicyclic graphs on

$10$ vertices. Let

$A$ be the adjacency matrix of any such graph.

asked 0 years ago

Anonymous

updated 0 years ago

Max Alekseyev

6932 ●9 ●52 ●162

Consider the class of simple connected bicyclic graphs on $10$ vertices. Let $A$ be the adjacency matrix of any such graph. Let $A(i)$ for $i\in{1,2,3,\ldots, 10}$ denote the principal submatrix of $A$ , obtained by deleting the $i$ -th row and $i$ -th column of $A$ . Now how to find those graphs from the collection for which nullity of $A(i)$ (for each $i=1,2,3,\ldots, 10$ ) is $1$ or equivalently rank of $A(i)$ (for each $i=1,2,3,\ldots, 10$ ) is $8$ .

My attempt:

def principal_submatrix(m, s, sort=False):
    if sort:
        s = sorted(s)
    return m[s, s]
def principal_submatrices(m, k):
    S = Subsets(range(m.ncols()), k)
    return [principal_submatrix(m, s, sort=True) for s in S]

for g in graphs.nauty_geng("10 -c"):
      if g.size() == 11:
          A=g.adjacency_matrix()

From this point, can any body please help me to complete the final code

Comments

Please help to complete the code, if possible. I am unable to extract the principal submatrices part.

rewi ( 0 years ago )

Your code will brute-force explore the set of all connected graphs of 10 vertices, a not-so-small subset of the set of all graphs on 10 vertices, of size 2^100, that is about 1.26*10^30. This seems unpractical, unless you want to build a generator of such graphs and get (a few) examples.

It seems faster and simpler to start from a simply connected acyclic graph (there are only 3628800 of them) and add them two cycles. You have to specify if you want those two cycles strictly separated or not and how you want them connected to the acyclic graph.

Emmanuel Charpentier ( 0 years ago )

I need only the bicyclic graphs on $10$ vertices. Even if you can write the code correctly, it will be fine for me.

rewi ( 0 years ago )

I was wrong about the size of the set of connected graphs on 10 vertices :

sage: foo=0
sage: %time for g in graphs.nauty_geng("10 -c"): foo+=1
CPU times: user 1min 43s, sys: 7.27 ms, total: 1min 43s
Wall time: 1min 43s
sage: foo
11716571

Sorry for the noise...

Emmanuel Charpentier ( 0 years ago )

No, it's fine.

rewi ( 0 years ago )

add a comment

answered 0 years ago

Emmanuel Charpentier
7804 ●8 ●52 ●155

updated 0 years ago

It turns out that the brute-force exploration is, in this case, not too long. Run :

def principal_submatrix(m, s, sort=False):
    if sort:
        s = sorted(s)
    return m[s, s]

# Generator of graphs conforming to requirements

def gen_bicycles():
    for g in graphs.nauty_geng("10 -c"):
        if g.size()==11:
            A=g.adjacency_matrix()
            if all(map(lambda s:bool(principal_submatrix(A, s, sort=True).rank()==8),
                       Subsets(g.vertices(), 9))):
                yield g

Then, the list of such graphs can be generated by :

sage: L=[]
sage: GB=gen_bicycles()
sage: %time for g in GB: L+=[g]
CPU times: user 1min 46s, sys: 32 ms, total: 1min 46s
Wall time: 1min 46s
sage: len(L)
171
sage: L[choice(range(len(L)))].plot()
Launched png viewer for Graphics object consisting of 22 graphics primitives

A random bicyclic graph in 10 vertices

HTH,

link

Comments

Can you please put the complete code in a single code? I have compiled your code but it is not compiling. Is your code giving all possible graphs on 10 vertices with 11 edges? Because I have a bicyclic graph on 10 vertices with two disjoint cycle having the required property but it is not coming in your code. Is there any problem.

Thanks

rewi ( 0 years ago )

I tried a lot to compile your code. But it is not going to compile. Can you please give the whole code in a single file.

rewi ( 0 years ago )

I have compiled your code but it is not compiling.

What is (are) the error(s) ?

Is your code giving all possible graphs on 10 vertices with 11 edges?

No. It starts with the set of all connex graphs on 10 vertices with 11 edges (the -c option passed to nauty). Then it selects the bicyclic graphs among them.

Because I have a bicyclic graph on 10 vertices with two disjoint cycle having the required property but it is not coming in your code. Is there any problem.

Is this graph connex ?

Emmanuel Charpentier ( 47 hours ago )

When I compile your code, the system can not give the graph as given by you. Can you please put your code in a single code. May be I am wrong in copying certain things that's why.

rewi ( 46 hours ago )

The following graph is a bicyclic graph on 10 vertices having the required property but this graph is not your list. Is there any problem.

G=graphs.EmptyGraph()
G.add_edges([(1,2),(2,3),(3,4),(5,4),(2,5),(6,5),(7,6),(8,7),(9,8),(9,6),(9,10)])
G.show()

rewi ( 46 hours ago )

see more comments

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 bicyclic graphs on $10$ vertices. Let $A$ be the adjacency matrix of any such graph.

Comments

1 Answer

Comments

Your Answer

Question Tools

Stats

Consider the class of simple connected bicyclic graphs on 1010 vertices. Let AA be the adjacency matrix of any such graph. savecancel

Comments

1 Answer

Comments

Your Answer

Question Tools

Stats

Consider the class of simple connected bicyclic graphs on $10$ vertices. Let $A$ be the adjacency matrix of any such graph.