software graph theory for finding graph with girth 3

Question

Is there any software for finding all graphs (edges and nodes) with girth(the girth of a graph is the length of a shortest cycle contained in the graph) three and diameter at least three?

The eccentricity of a vertex v is the greatest distance between v and any other vertex.

The diameter d of a graph is the maximum eccentricity of any vertex in the graph.

Answer 1

You can use nAUTy and tools for this:

./geng -cq 7 | ./countg -g3 -Z3:

This is using geng to generating all connected graphs on 7 vertices and filtering using countg all those with girth 3 (-g3) and diameter at least 3 (-Z3:).

To give an idea of how many there are, here is a table for n = 5 to 10:

 n   matches  total
 5       3       21
 6      37      112
 7     426      853
 8    6705    11117
 9  168197   261080
10 7589873 11716571

So there are only 426 graphs on 7 vertices out of 853 total, but 7,589,873 on 10 vertices.