Generation of graphs where all maximal cliques have the same size

22 views
Skip to first unread message

Christian Stump

unread,
Oct 19, 2017, 11:02:33 AM10/19/17
to sage-support
Hi,

how can I generate, in a fast enough way, connected graphs for which the clique complex is pure, ie, for which all containmentwise maximal cliques are of the same size ?

Fast enough here means that I can produce examples of such graphs with 20 vertices,  edge degrees between 10 and 14 (an example of such a graph on diagonals in a regular 7-gon with edges being pairwise noncrossing diagonals and the resulting clique complex the dual associahedron of dimension 4).

What I got so far is:

from sage.graphs.independent_sets import IndependentSets
for G in graphs.nauty_geng("20 -c -d10 -D14"):
    cliques = IndependentSets(G, maximal = True, complement = True)
    sizes = map(len,cliques)
    size_min = min(sizes)
    if size_min > 4:
        size_max = max(sizes)
        if size_min == size_max:
            print list(cliques)

But this seems to be too slow, already because it takes too long for this to turn the graph6 string from nauty into a sage graph.

Does someone know how I can do this computation more low-level? Best would clearly be to teach nauty to only iter through such graphs, but that does not seem to be possible...

Thanks, Christian

Jori Mäntysalo

unread,
Oct 19, 2017, 11:23:32 AM10/19/17
to sage-support
On Thu, 19 Oct 2017, Christian Stump wrote:

> But this seems to be too slow, already because it takes too long for this to
> turn the graph6 string from nauty into a sage graph.

Might be worth trying to use from_graph6 directly. Currenty nauty_geng()
says G = graph.Graph(s[:-1], format='graph6'), and the function for that
first does some checks and then does

if format == 'graph6':
if weighted is None: weighted = False
self.allow_loops(loops if loops else False, check=False)
self.allow_multiple_edges(multiedges if multiedges else False,
check=False)
from .graph_input import from_graph6
from_graph6(self, data)

I think that doing import in a loop might take some time in Python.

This won't help much, but maybe a little.

--
Jori Mäntysalo

Jori Mäntysalo

unread,
Oct 20, 2017, 2:27:14 AM10/20/17
to sage-support
On Thu, 19 Oct 2017, Jori Mantysalo wrote:

> Might be worth trying to use from_graph6 directly.

Tested. Don't bother, does not give really speedup that would mean
something.

--
Jori Mäntysalo

Dima Pasechnik

unread,
Oct 20, 2017, 4:48:49 AM10/20/17
to sage-support


On Thursday, October 19, 2017 at 4:02:33 PM UTC+1, Christian Stump wrote:
Hi,

how can I generate, in a fast enough way, connected graphs for which the clique complex is pure, ie, for which all containmentwise maximal cliques are of the same size ?

Reply all
Reply to author
Forward
0 new messages