[Nauty] database of small graphs (slightly off-topic)

Chad Brewbaker crb002 at iastate.edu
Fri Apr 29 13:43:02 EST 2005


What invarients do you want? I have C code (UNIX filters) that does all of the
following with a D after it. I am working on a database about the size of a CD
or DVD. I could host the code on Souceforge, but not untill mid May.(End of
semester crunch)  It's licenced under the GPL.  I need still need to create a
makefile, and I was going to add some data mining tools. 

While I am at it does anybody know an "fast" algorithm for minimum surface
embedding of a graph?  The best I could find is a clock face labeling algorithm
that runs in about O(n!^2), and the polynomial time ones for planar and toroidal
graphs.

-Chad Brewbaker

Invarient name:status(NS(not started),PC(Pseudocode),RC(real
code),T(testing),D(done):descrption

EDGE_CHROM:NS:Edge chromatic number
VERT_CHROM:D:Vertex chromatic number
AVE_GREEDY_VCHROM:Average greedy vertex coloring
TOTAL_CHROM:NS:Number of colors needed to color both edges and verticies such
that no adjacent edges and no adjacent verts share the same color
VERT_CHROM_COUNT:D:The number of vertex partitions that yield legal colorings.
VERT_ANTI_CHROM:D:Smallest number of partitions needed so that every partition
is a clique.
VERT_ANTI_CHROM_COUNT:D:The number of partitions such that every partition is a
clique.

MAX_CLIQUE:D:Largest induced complete graph
CLIQUE_NUM:D:The number of cliques in a graph
MAX_IND_SET:D:Largest set of verticies with no edges beteen them.
IND_SET_NUM:D:The number of independent sets
ALPHA_CORE:NS:The size of the intersection of all maximum independent sets.
VERT_COVER:D:Size of the minimum set of verticies that touch all other verticies.
EDGE_COVER:NS:Size of the minimum set of edges such that they touch all verticies
VERTEX_CONN:NS:Vertex connnectivity. The number of verticies that need to be
deleted to seperate or trivialize the graph.
EDGE_CONN:NS:Edge connectivity. The number of edges that need to be deleted to
seperate or trivialize the graph.

MIN_METRIC_DIM:D:A subset of verts such that every u,x in V there is a w in the
subset such that the length of the shortest path from u to w is different from
the length of the shortest path from x to w.
MIN_BANDWIDTH:D:Label verts 1,2,...,|V|. Bandwith is the edge with the greatest
difference in labels
MAX_BANDWIDTH:D:(THIS IS CRAP. IT is the same as the Number of verts-1 in a
connected graph*/
MIN_LINEAR_ARRANGEMENT:D:Label verts 1,2,...,|V|. Minimize sum of edge
differences in labels.
MAX_LINEAR_ARRANGEMENT:D:Label verts 1,2,...,|V|. Maximize sum of edge
differences in labels.
MIN_CUT_LINEAR_ARRANGEMENT:NS:
MIN_LINE_CROSSING:D:Draw the graph on a line with a vertex at points
1,2,...,|V|. Minimize number of edge crossings.
MAX_LINE_CROSSING:D:Draw the graph on a line with a vertex at points
1,2,...,|V|. Maximize number of edge crossings
MIN_CIRCLE_CROSSING:D:Draw the graph on equidistant points of a circle. Minimize
number of edge crossings.
MAX_CIRCLE_CRISSING:D:Draw the graph on equidistant points of a circle. Maximize
number of edge crossings.


MAX_IND_SEQUENCE:NS:
MAX_PLANAR_SUBGR:NS:The largest edge set that produces a planar graph.


MAX_2_COLOR_SUBGR:NS:The largest edge set that is 2 colorable
MAX_3_COLOR_SUBGR:NS:The largest edge set that is 3 colorable
MAX_K_COLOR_SUBGR:NS:The largest edge set that is K colorable
MAX_2_COLOR_IND_SUBGR:NS:Largest 2 colorable induced subgraph
MAX_3_COLOR_IND_SUBGR:NS:Largest 3 colorable induced subgraph
MAX_K_COLOR_IND_SUBGR:NS:Largest K colorable induced subgraph
MIN_EDGE_2_SPANNER:NS:
MIN_EDGE_3_SPANNER:NS:
MIN_EDGE_K_SPANNER:NS:
MIN_DOMINATING_SET:NS:Min subset of verticies such that for all u not in the
subset there is a v in the subset for which (u,v)\in E
MIN_ANTI_DOM_SET:NS:Min subset of  verticies such that for all u not in the
subset there is a v in the subset for which (u,v)\notin E
MIN_DOMATIC_PARTITION:NS:Smallest number of partitions of the vertcies such that
each partition is a dominating set.
MAX_DOMATIC_PARTITION:NS:Largest number of partitions of the vertcies such that
each partition is a dominating set.


/*Upgrades downgrades and completions*/
MIN_INTERVAL_COMPLETION:NS:The number of edges needed to be added/deleted to
make G a minimal interval graph.
MIN_CHORDAL_COMPLETION:NS:The number of edges needed to be added/deleted to make
G a minimal chordal graph
MIN_VCHROM_UPGRADE:NS:The number of edges needed to be added to up the vertex
chromatic number of the graph.
MIN_VCHROM_DOWNGRADE:NS:The number of edges needed to be deleted to make the
vertex chromatic number go down.
MIN_ECHROM_UPGRADE:NS:The number of edges to be added to upgrade the edge
chromatic number
MIN_ECHROM_DOWNGRADE:NS:The number of edges neede to be deleted to downgrade the
edge chromatic number
MIN_VCUT_UPGRADE:NS:The number of edges needed to be added to up the min vertex cut.
MIN_VCUT_DOWNGRADE:NS:The number of edges needed to be deleted to decrease the
min vertex cut.
MIN_ECUT_UPGRADE:NS:
MIN_ECUT_DOWNGRADE:NS:
IRREGULARITY:D:The sum of edge weights, where weight is defined as the
difference in degree.
LOVASZ_THETA:D:Lovasz number of the graph-> MAX_CLIQUE<=LOVASZ<=VERT_CHROM
VERT_CON:NS:The smallest number of verts needed to be deleted to disconnect the
graph
EDGE_CON:NS:The smallest number of edges needed to be deleted to disconnect the
graph
MAX_DEG:D:The largest neighborhood of any vertex
MIN_DEG:D:The smallest neighborhood of any vertex
EDGES:D:The number of edges in the graph
VERTS:D:The number of verticies in the graph
TRIANGLES:D:The number of triangles.
QUADS:D:The number of complete subgraphs on 4 verticies
SUB_KN:NS:Prints out the number of K_{n} subgraphs
VOLUME:NS:The sum of vertex degrees.
CHEEGER_CONST:NS:The minimum |Edges_betwen(S,\bar{S})|/min(vol S,vol \bar{S})
for a subset S of verticies, where vol S is the sum of vertex degrees.
ALPHA_DISC:NS:Alpha-discrepency. This is the maximum of all subsets of verticies
S, where |S|=floor(VERTS*alpha), |E(S,S)- (2e/n^2)*|S|^2|. (See Fan Chungs
spectral graph theory text)
ORBITS:T(lnk with nauty):The number of nonisomorphic vertex classes
MAX_ORBIT:T(lnk with nauty):The largest orbit
MIN_ORBIT:T(lnk with nauty):The smallest orbit


DISTANCE_SUM:D:The sum of distances between all pairs of verticies.
CLOSER_PRODUCT:D: let closer(u,v) be the number of verticies closer to u than v.
We want the sum over all edges (closer(u,v)*closer(v,u))
CLOSER_DIFF:D: let closer(u,v) be the number of verticies closer to u than v.
We want the sum over all edges ABS(closer(u,v)-closer(v,u))

DIAMETER:D:The greatest distance bewtween any two verticies in the graph
RADIUS:D:The vertex with the greatest distance to any other vertex minimized.
Radius is the distance.
CENTER_SUM:D:The vertex with the lowest sum of distances to all other verticies.
This sum is CENTER_SUM.
OUTER_SUM:D:The vertex with the highest sum of distances to all other verticies.
This sum is OUTER_SUM. 
TREE_WIDTH:NS: Smallest width of a tree decomposition. A tree decomposition is a
tree T and a family V of vertex sets such that:
1. The union of families of each vertex in the tree equals all verticies.
2. Every edge of G has both ends in some Y_t

3. If x,y,z are in V(T) and y lies on the path between x and z, then Y_x\cap Y_z
\subseteq Y_y
Width= max$\{|V_{t}|:t\inT\}$


PATH_WIDTH:NS:
CLIQUE_WIDTH:NS:The clique width of the graph
BRANCH_WIDTH:NS:The branch width of the graph
MAX_CYCLE:D:Largest cycle in the graph. 0 if no 3 or bigger cycle is
found.(Circumfrence)
MIN_CYCLE:D:MINIMAL CYCLE. 0 if no three or bigger cycle is found (Girth)
CYCLE_NUM:D:The number of cycles in the graph.
ODD_CYCLES:D:The number of odd cycles.
CYCLE_PACKING:PC:The maximum number of edge disjoint cycles in the graph. 
RADIO_CHROM:NS:Radio chromatic number
COSTAS_DIM:NS:The minmium size square matrix the adjacency matrix can be
embedded in such that every pair of points creates a unique angle.
DETERMANENT:NS:The determinant of the adjacency matrix.
PERMANENT:NS:The permanent of the adjacency matrix.
BLOCKS:NS:The number of maximal connected subgraphs of G that have no cut-vertex.
BRIDGES:NS:The number of cut edges in the graph. 

PEB_NUM:NS:Pebbling number
(From every configuration of \pi pebbles on V it is possible to place a pebble on a
ny specified target vertex after a sequence of pebbling moves. We want the minimum 
number of pebbles needed so that no matter how they are placed any vertex can be pe
bbled by taking two pebbles off a vertex, sacrificing one, and moving the other peb
ble to an adjacent vertex.



MIN_MARTIN_CODE:D:Martins paper. The smallest set C of the verticies such that
BALL(V)\cap C is nonempty, and for two verts i,j  BALL(i)\cap C != BALL(j)\cap C
MARTIN_CODES:NS:The number of nonisomorphic maritin codes.
MIN_FLOW:NS:The minimal flow betwen any two verts in the graph.
MAX_FLOW:NS:The max flow between any two verts in the graph
DECKS:NS:Number of nonisomorphic graphs resulting from the deltion of single verts
VERT_COLORS:NS:Nuber of nonisomorphic vertex colorings
EDGE_COLORS:NS:Number of nonisomorphic edge colorings
VERT_EDGE_COLORS:NS:Number of nonisomorphic vertex and edge colorings
SPAN_TREES:NS:Number of spanning trees
SPAN_TREES_ISO:NS:Number of nonisomorpic spanning trees
CON_SUBGR:NS:Number of connected subgraphs
CON_SUBGR_ISO:NS: Number of nonisomorphic connected subgraphs
IND_CON_SUBGR:NS:Number of induced connected subgraphs
IND_CON_SUBGR_ISO:NS:Number of nonisomorphic induced connectedsubgraphs
KOCKAY_PARTITIONS:D:The number of partions created by repeatedly spliting
partions based on their number of edges to current partitoins in the graph.
DISTANCE_PARTITIONS:NS:How many partitions are formed by splitting the verticies
on differences in distances between a partion and other partitions. This is a
subpartition of KOCKAY partitioning.
TRIANGLE_PARTITIONS:NS:How many partitions are formed by splitting verticies
based on the number of triangles they belong to.
QUAD_PARTITIONS:NS:How many partitions are formed by splitting verticies based
on the number of copies of K4  they belong to.
VERT_DEG_PARTITIONS:NS:How many partitions are formed by splitting on vertex degree.

MIN_GENUS:D:(But REALLY SLOW)The surface with the least holes that has an
orientable emedding in.
(Open Problem from Mohar and Thomassen: genus(K_{3,3,3,3})? Is
genus(K_{3,3,3,3})<4?)
http://www.csr.uvic.ca/~wendym/torus/embedding.html


MAX_GENUS:NS:The largest orientable surface the graph can be embeded on.

MAX_PAIR_EAR_DECOMP:NS:
MORSE_SMALE_FLOWS:NS:

GAME_CHROM:NS:The game chromatic number
Two players, Alice and Bob, alternately colour the vertices of a graph G with
colours from a colour set C. Adjacent vertices must be coloured by distinct
colours. The game ends if either all vertices are coloured or there is no legal
colour for the remaining uncoloured vertices. Alice wins the game if all
vertices are coloured, and Bob wins otherwise. The game chromatic number of G is
the least number of colours in the colour set C so that Alice has a winning
strategy for this game. The problem of calculating the game chromatic number of
planar graphs first appeared in Martin Gardner's columns "Mathematical Games"
(contributed by Steven Brams) in 1981. In 1991, it was independently introduced
by Hans Bodlaender, whose interest was to study the complexity of the game. In
recent years, the problem has attracted some attention from graph theorists,
where the main interest is the maximum values of the game chromatic number for
various classes of graphs. In this talk, I will explain a particular strategy
for Alice to play such a game. For many classes of graphs, including forests,
outerplanar graphs, planar graphs, partial k-trees, the best upper bounds on the
game chromatic number are proved by using this strategy. 

DISTINCT_EIGENVALUES:NS:The number of distinct eigenvalues in the unit edge
weighted graph.

/*Rational number invarients output is two integers on a line seperated by
whitespace */
FRAC_CHROM_NUM:NS:The fractional vertex chromatic number
AVE_ORBIT:NS:The average size of the orbits in a graph.
MAX_EIGENVALUE:NS:
MIN_EIGENVALUE:NS:
AVE_EIGENVALUE:NS:


/*Real valued invarients (Of course chopped to some precision)*/
RANDIC_INDEX:D:Sum of vertex edge where weight of edge xy is 1/(sqrt(deg(x)*deg(y)))

> Well, in the offline world there is the "Atlas of Graphs" though it only 
> goes up to 7 vertices for all graphs, I think (and higher for spedcial 
> classes).
> 
> Cheers,
> 
> On Thu, 28 Apr 2005, Jason Grout wrote:
> 
> > I've been using geng in my research to generate graphs with various 
> > properties.  I'd like to make it easier for my advisor to list the graphs 
> > that have certain properties.  I've already started working on a database of 
> > small graphs (under 10 vertices or so), generated using geng.  The idea is to 
> > create a web interface to the database that allows querying for graphs with 
> > certain properties.  I know some of you have listings of graphs with specific 
> > properties, but is there some publicly accessible database of all small 
> > graphs and the various properties of each one?  Preferably the database would 
> > allow queries over the web and would present the results in a format easily 
> > usable for people without a lot of computer skills.
> >
> > Thanks,
> > Jason
> > --
> > Jason Grout
> > grout at math.byu.edu
> >
> >
> > _______________________________________________
> > This is the nauty mailing list
> > Post messages to nauty-list at cs.anu.edu.au
> > nauty page: http://cs.anu.edu.au/~bdm/nauty/
> > list page: http://cs.anu.edu.au/mailman/listinfo/nauty-list
> >
> 
> _______________________________________________
> This is the nauty mailing list
> Post messages to nauty-list at cs.anu.edu.au
> nauty page: http://cs.anu.edu.au/~bdm/nauty/
> list page: http://cs.anu.edu.au/mailman/listinfo/nauty-list
> 









More information about the Nauty mailing list