Database of Graphs

[Jim Nastos]

On Sat, 30 Nov 2002, Felix Goldberg wrote:

> Well, there is the "Atlas of Graphs" on paper.  I guess that a
> sufficiently dedicated team with ample resources could handle the task of
> translating it into some electronic format.

  Still, I think there is much use in having 100-or-so properties and 
which graphs have those properties in a database and being able to 
intersect properties. The atlas doesn't provide that. A table of graphs 
that do not contain a certain small induced subgraph would be nice (for 
each small subgraphs.) Asking for graphs that have no C4 intersect graphs 
with no C5 intersect graphs with no 2K2 and asking for a common property 
of these graphs would yield the fact that they are all split graphs, for 
example, and would give a very strong indication that (C4, C5, 2K2)-free 
graphs are split (indeed, they are exactly the split graphs.)
  There are tonnes of graph classes that are still looking for good 
characterizations (e.g. asteroidal triple-free, weakly chordal graphs is 
one I've thought a bit about.) The approaches towards AT-free graphs are 
very different from those used in studying weakly chordal graphs, but 
their intersection is an interesting class that is still looking for 
publishable results. A database could provide an excellent initial 
direction in the investigation. I know I don't want to draw up all these 
graphs up to 10 vertices and look for common properties...
  If anyone else out there sees a use in this and is interested in maybe 
starting to build something useful, let me know. Maybe the integer 
sequence crowd is not the right one to be asking about this, but I think 
OEIS could eventually incorporate such functionality.

Jim Nastos



MIME-Version: 1.0