Various constructions of graphs that I have encountered in my research.
Currently, the scripts are undergoing reorganization into a proper GAP package. The GRAPE package for GAP is required.
The following graphs are currently supported:
- Classical distance-regular graphs:
- Hamming graphs H(d, e) with hypercubes H(d, 2) as special cases
- Halved cubes 1/2 H(d, 2)
- Doob graphs Doob(n, d) of diameter 2n+d
- Bilinear forms graphs Hq(d, e)
- Hermitean forms graphs Her(d, r)
- Grassmann graphs Jq(n, d)
- Twisted Grassmann graphs TGd(q)
- Dual polar graphs Bd(q)
- Dual polar graphs Cd(q)
- Dual polar graphs Dd(q)
- Dual polar graphs 2Dd+1(q)
- Dual polar graphs 2Ae(q) of diameter [e/2]
- the Gosset graph with intersection array {27, 10, 1; 1, 10, 27}
- the large Witt graph with intersection array {30, 28, 24; 1, 3, 15}
- the truncated Witt graph with intersection array {15, 14, 12; 1, 1, 9}
- Distance-regular graphs associated to finite geometries:
- incidence graphs of Desarguesian projective planes
- incidence graphs of Hall projective planes
- incidence graphs of Hughes projective planes (both ordinary and exceptional)
- collinearity graphs of generalized quadrangles Q(d, q) of order (q, qd-3) for d = 3, 4, 5
- collinearity graphs of generalized quadrangles H(d, r) of order (r2, rd-5/2) for d = 3, 4
- collinearity graphs of generalized quadrangles W(q) of order (q, q)
- collinearity graphs of generalized quadrangles AS(q) of order (q-1, q+1)
- collinearity graphs of derived generalized quadrangles Td(O) of order (q, qd-1)
- collinearity graphs of derived generalized quadrangles T*(O) of order (2h-1, 2h+1)
- collinearity graphs of derived generalized quadrangles P(S, x) of order (s-1, s+1)
- Other infinite families of distance-regular graphs:
- Cycles C(n)
- Complete Taylor graphs, i.e. Kn,n minus a matching
- Odd graphs O(d)
- Folded Johnson graphs J̃(2d, d)
- Folded cubes H̃(d, 2)
- Folded halved cubes 1/2 H̃(2d, 2)
- Doubled Odd graphs 2J(2d+1, d)
- Doubled Grassmann graphs 2Jq(2d+1, d)
- unitary nonisotropics graphs with intersection arrays {q2-q, q2-q-2, q+1; 1, 1, q2-2q}
- the Brouwer "vector product" graphs Br(q) with intersection arrays {q3-1, q3-q, q3-q2+1; 1, q, q2-1}
- the Pasechnik graphs Pa(q) with intersection arrays {q3, q3-1, q3-q, q3-q2+1; 1, q, q2-1, q3}
- coset graphs of Kasami codes
- de Caen, Mathon and Moorhouse's Preparata graphs Pr(t, e) (h = 1) and their quotients (h > 1) with intersection arrays {22t-1, 22t-2h, 1; 1, 2h, 22t-1}
- additive symplectic covers of complete graphs (j = i) and their quotients (j < i) with intersection arrays {pni-1, pni-pni-j, 1; 1, pni-j, pni-1}
- multiplicative symplectic covers of complete graphs with intersection arrays {q, q-m-1, 1; 1, m, q} (q or m even, m divides q-1)
- Families of strongly regular graphs:
- Cocktail party graphs
- Paley graphs
- Latin square graphs
- polar graphs O(±)(d, q)
- polar graphs NO±⊥(d, q)
- polar graphs Sp(d, q)
- polar graphs U(d, r)
- affine polar graphs VO±(2e, q)
- affine polar graphs VNO±(2e, q)
- Sporadic and other named distance-regular graphs:
- the Heawood graph with intersection array {3, 2, 2; 1, 1, 3}
- the skeleton of the cube with intersection array {3, 2, 1; 1, 2, 3}
- the skeleton of the icosahedron with intersection array {5, 2, 1; 1, 2, 5}
- the Sylvester graph with intersection array {5, 4, 2; 1, 1, 4}
- the Perkel graph with intersection array {6, 5, 2; 1, 1, 3}
- the Doro graph on 65 vertices with intersection array {10, 6, 4; 1, 2, 5}
- the Doro graph on 68 vertices with intersection array {12, 10, 3; 1, 3, 8}
- the bipartite graph associated to Higman's design with intersection array {50, 49, 36; 1, 14, 50}
- the Coxeter graph with intersection array {3, 2, 2, 1; 1, 1, 1, 2}
- the doubly truncated Witt graph with intersection array {7, 6, 4, 4; 1, 1, 1, 6}
- the skeleton of the dodecahedron with intersection array {3, 2, 1, 1, 1; 1, 1, 1, 2, 3}
- the Desargues graph with intersection array {3, 2, 2, 1, 1; 1, 1, 2, 2, 3}
- the Biggs-Smith graph with intersection array {3, 2, 2, 2, 1, 1, 1; 1, 1, 1, 1, 1, 1, 3}
- Named strongly regular graphs:
- the skeleton of the tetrahedron with v = 4, k = 3, λ = 2
- the skeleton of the octahedron with v = 6, k = 4, λ = 2, μ = 4
- the Petersen graph with v = 10, k = 3, λ = 0, μ = 1
- the Shrikhande graph with v = 16, k = 6, λ = 2, μ = 2
- the Clebsch graph with v = 16, k = 10, λ = 6, μ = 6
- the Schläfli graph with v = 27, k = 16, λ = 10, μ = 8
- the three Chang graphs with v = 28, k = 12, λ = 6, μ = 4
- the Hoffman-Singleton graph with v = 50, k = 7, λ = 0, μ = 1
- the Gewirtz graph with v = 56, k = 10, λ = 0, μ = 2
- the graph with v = 77, k = 16, λ = 0, μ = 4 associated to S(3, 6, 22)
- the graph with v = 210, k = 99, λ = 48, μ = 45 constructed by M. Klin
- Other graphs:
- Complete multipartite graphs
- Kneser graphs Kn(n, k)
- Graph derivation:
- Box (Cartesian) product
- Cross (tensor) product
- Strong product
- Bipartite double
- Extended bipartite double
- Halved graphs
- Antipodal quotients
- Clique graphs
- Vertex-clique incidence graphs
- Graphs from files:
- incidence graphs from files as listed on E. Moorhouse's webpage on projective planes or generalized polygons
- collinearity graphs from files as listed on E. Moorhouse's webpage on generalized polygons
- graphs in graph6, sparse6 and auto6 formats
Some constructions, such as complete graphs, Johnson graphs and Cayley graphs, are already available in GRAPE.