Database of Graphs

Jim Nastos nastos at
Fri Nov 29 18:26:51 CET 2002

Hi all.
  There are hundreds of studied graph classes defined as the collection of 
graphs sharing some useful or interesting property. In my discussions with 
another about certain classes, I was asking about what 9 or 10 vertex 
graphs are still in this specific class which can be formed by extending a 
certain 8-vertex graph in the class. He suggested that there should be a 
database for these types of queries.

  Here is a suggested project, which is fairly similar to OEIS: form a 
database of unlabelled small connected graphs along with some 
hundred-or-so properties such that one could query the databse with 
something like: "return all graphs on n vertices with properties P1, P2" 
or "I have these 5 graphs; what previously-studied properties do they have 
in common?"

  Of course, the table won't be able to exhaustively contain everything 
for n past, say, 12, but users could always add graphs that come up in
their problems that may be interesting. Even going up to just 11 vertices 
could make it a useful tool for researchers in many fields.

  Suggestions? Comments? Taker? Is there such a thing already? Could OEIS 
create a standard encoding of graphs into integers and incorporate that 
into the database? 

Jim Nastos

More information about the SeqFan mailing list