Ask Your Question
1

Maximum algebraic connectivity from a given collection of graphs

asked 2019-05-18 13:50:19 -0500

anonymous user

Anonymous

updated 2019-05-19 11:28:06 -0500

slelievre gravatar image

A connected graph on $n \ge 1$ vertices is cyclic (or unicyclic) if it has $n$ edges, bicyclic if it has $n + 1$ edges.

The following code runs through all connected graphs on 8 vertices with 9 edges, and shows each graph as well as the sorted list of its laplacian eigenvalues.

for g in graphs.nauty_geng("8 -c"):
    if g.size() == 9:
        g.show()
        h = g.laplacian_matrix().eigenvalues()
        h.sort()
        show(h)

How could one get the list of graphs whose algebraic connectivity (i.e. second smallest laplacian eigenvalue) is the maximum among those (the maximum here being $1$)?

edit retag flag offensive close merge delete

Comments

@rburing -- I had missed that. Indeed the answer there adapts to the question here.

slelievre gravatar imageslelievre ( 2019-05-21 05:04:01 -0500 )edit

1 answer

Sort by ยป oldest newest most voted
0

answered 2019-05-19 11:34:58 -0500

slelievre gravatar image

updated 2019-05-21 05:38:47 -0500

[Edited to take comments into account.]

Bicyclic graphs with top algebraic connectivity

One can construct the list using Nauty's generator and filtering by the desired conditions.

Note that Nauty's generator can already filter by minimum and maximum number of edges using mine:maxe (for "minimum number of edges", "maximum number of edges") -- thanks to @rburing for pointing this out; see note below on ways to browse the documentation.

There are 236 bicyclic graphs on 8 vertices:

sage: bicy8 = [g for g in graphs.nauty_geng("8 9:9 -c")]
sage: len(bicy8)
236

For a given graph g, its algebraic connectivity is the second smallest laplacian eigenvalue, so it can be obtained as sorted(g.laplacian_matrix().eigenvalues())[1].

Compute their algebraic connectivity, and the top algebraic connectivity:

sage: ac = [sorted(g.laplacian_matrix().eigenvalues())[1] for g in bicy8]
sage: tac = max(ac)
1

Extract graphs with top algebraic connectivity:

sage: gg = [g for i, g in enumerate(bicy8) if ac[i] == tac]

There are three:

sage: len(gg)
3

Their edges:

sage: for g in gg:
....:     print(g.edges(labels=None))
....:
[(0, 6), (0, 7), (1, 6), (1, 7), (2, 7), (3, 7), (4, 7), (5, 7), (6, 7)]
[(0, 5), (0, 7), (1, 6), (1, 7), (2, 7), (3, 7), (4, 7), (5, 7), (6, 7)]
[(0, 3), (0, 6), (1, 4), (1, 6), (2, 5), (2, 6), (3, 7), (4, 7), (5, 7)]

Show them:

sage: for g in gg:
....:     g.show()

Documentation of Nauty's graph generator

The documentation is available via any of the following solutions, which respectively give the documentation in text mode, the full source code in text mode, and the documentation in html mode:

$ graphs.nauty_geng?
$ graphs.nauty_geng??
$ browse_sage_doc(graphs.nauty_geng)

The html documentation can also be browsed locally (at least if you installed from source or from binaries from the Sage download pages) by pointing a browser to SAGE_ROOT/local/share/doc (where SAGE_ROOT denotes the root directory of your local Sage installation).

Or see the online SageMath documentation (html or pdf).

To avoid storing a long list graphs

To avoid storing all bicyclic graphs on 8 vertices in a list, one could run through them, keeping and updating a current value of the top algebraic connectivity and a current list of graphs achieving it.

sage: tac = 0
sage: gtac = []
sage: for g in graphs.nauty_geng("8 9:9 -c"):
....:     ac = sorted(g.laplacian_matrix().eigenvalues())[1]
....:     if ac == tac:
....:         gtac.append(g)
....:     elif ac > tac:
....:         tac, gtac = ac, [g]

In the end we get the top algebraic connectivity:

sage: tac
1

and know how many graphs achieve it:

sage: len(gtac)
3

and we can show their edges:

sage: [g.edges(labels=None) for g in gtac]
[[(0, 6), (0, 7), (1, 6), (1, 7), (2, 7), (3, 7), (4, 7), (5, 7), (6, 7)],
 [(0, 5), (0, 7), (1, 6), (1, 7), (2, 7), (3, 7), (4, 7), (5, 7), (6, 7)],
 [(0, 3), (0, 6), (1, 4), (1, 6), (2, 5), (2, 6), (3, 7), (4, 7), (5, 7)]]

or visualize them:

sage: for g in gtac:
....:     g.show(layout='circular')

Note there are other options for visualization, including:

  • g.show(layout='circular')
  • g.show(layout='planar')
  • g.show(method='js')

Defining a function

The code above can be turned into a function of the number of vertices:

def top_alg_conn(n):
    m = n + 1
    tac = 0
    gtac = []
    for g in graphs.nauty_geng("{} {}:{} -c".format(n, m, m)):
        ac = sorted(g.laplacian_matrix().eigenvalues())[1]
        if ac == tac:
            gtac.append(g)
        elif ac > tac:
            tac, gtac = ac, [g]
    return tac, gtac

For 9 vertices this might take something like 10 seconds:

sage: tac, gtac = top_alg_conn(9)
sage: tac, len(gtac)
(1, 2)
sage: for g in gtac:
....:     print(g.edges(labels=False))
[(0, 7), (0, 8), (1, 7), (1, 8), (2, 8), (3, 8), (4, 8), (5, 8), (6, 8), (7, 8)]
[(0, 6), (0, 8), (1, 7), (1, 8), (2, 8), (3, 8), (4, 8), (5, 8), (6, 8), (7, 8)]

For 10 vertices this might take on the order of 30 seconds:

sage: tac, gtac = top_alg_conn(10)
sage: tac, len(gtac)
(1, 2)
sage: for g in gtac:
....:     print(g.edges(labels=False))
[(0, 8), (0, 9), (1, 8), (1, 9), (2, 9), (3, 9), (4, 9), (5, 9), (6, 9), (7, 9), (8, 9)]
[(0, 7), (0, 9), (1, 8), (1, 9), (2, 9), (3, 9), (4, 9), (5, 9), (6, 9), (7, 9), (8, 9)]

For 11 vertices this might take on the order of 2 minutes:

sage: %time tac, gtac = top_alg_conn(11)
CPU times: user 2min 5s, sys: 960 ms, total: 2min 6s
Wall time: 2min 9s

sage: tac, len(gtac)
(1, 2)
sage: for g in gtac:
....:     print(g.edges(labels=False))
[(0, 9), (0, 10), (1, 9), (1, 10), (2, 10), (3, 10), (4, 10), (5, 10), (6, 10), (7, 10), (8, 10), (9, 10)]
[(0, 8), (0, 10), (1, 9), (1, 10), (2, 10), (3, 10), (4, 10), (5, 10), (6, 10), (7, 10), (8, 10), (9, 10)]

And so on...

edit flag offensive delete link more

Comments

actually I do not need all these graphs. I need those graphs only whose algebraic connectivity is maximum among these 30 graphs.

Kuldeep gravatar imageKuldeep ( 2019-05-19 13:07:01 -0500 )edit

Sorry, sorted now!

slelievre gravatar imageslelievre ( 2019-05-19 19:04:01 -0500 )edit
1

Ok.fine. Now if we do not give the input 1(that is, the algebraic connectivity value) and keep it for sage to evaluate which graphs has the maximum algebraic connectivity from the collection and then show those graphs, is it possible to do so?

Kuldeep gravatar imageKuldeep ( 2019-05-20 00:12:44 -0500 )edit

It's more efficient to let nauty restrict the number of edges: list(graphs.nauty_geng("8 9:9 -c")).

rburing gravatar imagerburing ( 2019-05-20 04:44:52 -0500 )edit
1

@rburing -- I thought that should be possible but missed that part of the documentation when I read it to answer the question... Thanks for coming to the rescue; I edited my answer accordingly.

@Kuldeep -- see revised answer, no longer assuming prior knowledge of the top algebraic connectivity.

slelievre gravatar imageslelievre ( 2019-05-21 04:42:05 -0500 )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: 2019-05-18 13:50:19 -0500

Seen: 132 times

Last updated: May 21