Benchmark

In this benchmark we include different graph families, both of graphs and digraphs. For each family we consider graphs with up to one thousand vertices (approximately). Some of them have two non-isomorphic instances of each size. The format of the graph files (SIVALab) is described here.

Strongly Regular Graphs

  • Steiner Triple Systems graphs. This STS family is part of the "sts" series of the bliss benchmark. These are the line graphs srg(v(v--1)/6, 3(v--3)/2, (v+3)/2, 9) of Steiner triple systems which have (v(v+1)-2)/18 orbits.
  • Latin square graphs. This family is the "latin" series of the bliss benchmark. This family consists of Latin square graphs srg(n2, 3(n-1), n, 6), where n is the order of the graphs. We have classified them in two subfamilies: those of prime order, and those of prime power order. Prime power order Latin square graphs are usually harder for graph isomorphism testing algorithms than those of prime order.
  • Paley graphs. These are strongly regular graphs srg(q, (q-1)/2, (q-5)/4, (q-1)/4), where q is the order of the graphs. We have classified them in two subfamilies: those of prime order, and those of prime power order. Prime power order graphs are usually harder than prime order ones.
  • Lattice graphs. These are strongly regular graphs srg(n2, 2(n-1), n-2, 2).
  • Triangular graphs. These are strongly regular graphs srg(q(q-1)/2, 2(q-2), q-2, 4).
Component-Based Graphs
  • Unions of Strongly Regular Graphs. The graphs of this USR family are built using some Strongly Regular Graphs srg(29, 14, 6, 7) as basic components. Each vertex of each component is connected to all the vertices of all the other components. These graphs are extremely dense.
  • Cubic Hypo-Hamiltonian clique-conected. This CHH family is built using as basic components two non-isomorphic cubic Hypo-Hamiltonian graphs with 22 vertices. Both graphs have four orbits of sizes: one, three, six, and twelve. A graph CHH_cc(m,n) has n complex components built from m basic components. The components of a complex component are connected through a complete m-partite graph using the vertices that belong to the orbits of size three of each basic component. The n complex components are interconnected with a complete n-partite graph using the vertices of each complex component that belong to the orbits of size one in the basic components.
  • Non-Disjoint Unions of Directed Tripartite graphs. We take two non-isomorphic digraphs with 13 vertices as basic components. Each of these components has 4 vertices with out-degree 3, 6 vertices with in-degree 4, and 3 vertices with out-degree 4. Then, each graph in the TND family tnd(n) is generated taking n pairs of components, and joining them by adding, for each vertex with out-degree 4, out-arcs connecting it to all the vertices with out-degree 3 of the other components of the graph.
  • Non-Disjoint Unions of Undirected Tripartite graphs.This TNN family is the undirected version of the TND family.
Graphs based on Miyazaki's construction
  • Base Construction. The MZN family contains the original contruction of Miyazaki, not considering colours. The MZD family is a directed version of the base construction of Miyazaki.
  • CMZ. This CMZ family is the "cmz" series of the bliss benchmark. It is a variant of the original Miyazaki's construction.
  • Switched. The MSN family is obtained from the original construction of Miyazaki, changing one bridge for a switch. The MSD family is the corresponding directed versión of the MSN family.
  • Augmented. The MZA and the MA2 families are, respectively, the "mz-aug" series and "mz-aug2" series of the bliss benchmark.
Other graph families
  • Affine Geometries. This AG2 family is the "ag" series of the bliss benchmark. It contains point-line graphs of affine geometries AG2(q).
  • Complete graphs. The  COM family contains simple undirected graphs, in which every pair of distinct vertices is connected by an edge.
  • Desarguesian Projective planes. The PG2 family contains the point-line graphs of Desarguesian projective planes PG2(q).
  • F-Lex. The F-LEX graphs have been built by Petteri Kaski following a construction due to Pascal Schweitzer.
  • Hadamard. The HAD family conatains graphs defined in terms of a Hadamard Matrix. It also includes the "had" series
    of the bliss benchmark.
  • Hadamard-Switched. The HSW family is the "had-sw" series of the bliss benchmark.
  • Kronecker Eye Flip graphs. This KEF family comes from the "kef" series of the bliss benchmark.
  • Line graphs of Complete graphs. The LKG family contains the line-graphs of Complete graphs.
  • Paley Tournaments. The PTO family contains Paley tournaments (digraphs). The vertices of a paley tournament are the elements of the finite field Fq. There is an arc from vertex a to vertex b if and only if a - b is a quadratic residue in Fq.
  • Projective Planes (Order 16). The PP16 family contains the projective planes described in http://www.uwyo.edu/moorhouse/pub/planes16/.
  • Random graphs. The R1D family comes from the SIVALab benchmark. These are graphs in which there is an arc from a vertex u to a vertex v with probability 0.1. The R1N is the undirected version of the R1D family.
  • Two-Dimensional Grids. The G2D family comes from the SIVALab benchmark. These are the two-dimensional meshes in that benchmark. The G2N family is the undirected version of the G2D family.