implicity

i am looking for the number of digraphs on 6 vertices, where every vertex can be reached from every other by following the edges in the right direction, and the graph is minimal with this property; ie., if you remove any single edge, you can no longer reach every vertex from every other vertex. i don't know whether this property (the first property, not the minimal property) has a name (connected digraph?). if you can get one such graph from another one by swapping round vertices, i consider them to be the same, or in other words, i'm counting unlabelled, not labelled graphs.

the dumbest kind of brute force (checking every digraph on 6 vertices) would give about 1 billion graphs to check for connectedness, minimality, and whether they are variations on each other. analysing and counting 1 billion graphs quickly is quite feasible. it's storing them and then comparing them to each other which almost immediately becomes practically impossible. in fact, storing a billion graphs is only slightly out my reach, but comparing them to each other is prohibitive. so it's necessary to come up with simplifications. the first of these are very quick and often rewarding - the low-hanging fruit. for example trying only a full set of unlabelled graphs, however many there are on 6 vertices, for the set of arrows in each direction. or ordering the graphs so that each one comes before all the ones which have the same edges plus some more, so that we find the minimal connected one first, and then don't need to bother with the rest. after that optimizations become a little more tricky. we start to have to use graph theory or symmetries in clever ways. (not withstanding the fact that the set of symmetries of 6 unlabelled points has no particular characteristics whatsoever - it's just the set of permutation of six items.) the universal tradeoff between computer time and programmer time comes into play, and every cpu clock tick has to be measured off against the more limited, and potentially more valuable, heartbeats and ticks of the human brain..

right now though, i do not have the time. someone do this for me please.

edit: a digraph where you can reach every vertex from every other is called strongly connected.

# posted by weierstrass @ 03:20