Database of distance regular graphs¶
In this module we construct several distance regular graphs and group them in a function that maps intersection arrays to graphs.
For a survey on distance-regular graph see [BCN1989] or [VDKT2016].
EXAMPLES:
sage: G = graphs.cocliques_HoffmannSingleton()
sage: G.is_distance_regular()
True
AUTHORS:
Ivo Maffei (2020-07-28): initial version
-
sage.graphs.generators.distance_regular.
AlternatingFormsGraph
(n, q)¶ Return the alternating forms graph with the given parameters.
This builds a graph whose vertices are all \(n\) skew-symmetric matrices over \(GF(q)\) with zero diagonal. Two vertices are adjacent if and only if the difference of the two matrices has rank 2.
This grap is distance-regular with classical parameters \((\lfloor \frac n 2 \rfloor, q^2, q^2 - 1, q^{2 \lceil \frac n 2 \rceil -1})\).
INPUT:
n
– integerq
– a prime power
EXAMPLES:
sage: G = graphs.AlternatingFormsGraph(5, 2) # long time sage: G.is_distance_regular(True) # long time ([155, 112, None], [None, 1, 20])
REFERENCES:
See [BCN1989] pp. 282-284 for a rather detailed discussion, otherwise see [VDKT2016] p. 22.
-
sage.graphs.generators.distance_regular.
BilinearFormsGraph
(d, e, q)¶ Return a bilinear forms graph with the given parameters.
This builds a graph whose vertices are all \(d\) matrices over \(GF(q)\). Two vertices are adjacent if the difference of the two matrices has rank 1.
The graph is distance-regular with classical parameters \((\min(d, e), q, q-1 , q^{\max(d, e)}-1)\).
INPUT:
d, e
– integers; dimension of the matricesq
– integer; a prime power
EXAMPLES:
sage: G = graphs.BilinearFormsGraph(3, 3, 2) sage: G.is_distance_regular(True) ([49, 36, 16, None], [None, 1, 6, 28]) sage: G = graphs.BilinearFormsGraph(3,3,3) # not tested (20 s) sage: G.order() # not tested (due to above) 19683 sage: G = graphs.BilinearFormsGraph(3, 4, 2) # long time sage: G.is_distance_regular(True) # long time ([105, 84, 48, None], [None, 1, 6, 28])
REFERENCES:
See [BCN1989] pp. 280-282 for a rather detailed discussion, otherwise see [VDKT2016] p. 21.
-
sage.graphs.generators.distance_regular.
ConwaySmith_for_3S7
()¶ Return the Conway-Smith graph related to \(3 Sym(7)\).
This is a distance-regular graph with intersection array \([10, 6, 4, 1; 1, 2, 6, 10]\).
EXAMPLES:
sage: G = graphs.ConwaySmith_for_3S7() sage: G.is_distance_regular(True) ([10, 6, 4, 1, None], [None, 1, 2, 6, 10])
REFERENCES:
A description and construction of this graph can be found in [BCN1989] p. 399.
-
sage.graphs.generators.distance_regular.
DoubleGrassmannGraph
(q, e)¶ Return the bipartite double of the distance-\(e\) graph of the Grassmann graph \(J_q(n,e)\).
This graph can also be descirbed as follows: Let \(V\) be the vector space of dimension \(n\) over \(GF(q)\). The vertex set is the set of \(e+1\) or \(e\) subspaces of \(V\). Two vertices are adjacent if one subspace is contained in the other.
This graph is distance-transitive.
INPUT:
q
– a prime powere
– integer
EXAMPLES:
sage: G = graphs.DoubleGrassmannGraph(2,1) sage: G.diameter() 3 sage: G.is_distance_regular(True) ([3, 2, 2, None], [None, 1, 1, 3])
REFERENCES:
See [BCN1989] pp. 272, 273 or [VDKT2016] p. 25.
-
sage.graphs.generators.distance_regular.
DoubleOddGraph
(n)¶ Return the double odd graph on \(2n+1\) points.
The graph is obtained using the subsets of size \(n\) and \(n+1\) of \({1, 2, ..., 2n+1}\) as vertices. Two vertices are adjacent if one is included in the other.
The graph is distance-transitive.
INPUT:
n
– integer; must be greater than 0
EXAMPLES:
sage: G = graphs.DoubleOddGraph(5) sage: G.is_distance_regular(True) ([6, 5, 5, 4, 4, 3, 3, 2, 2, 1, 1, None], [None, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6]) sage: G = graphs.DoubleOddGraph(3) sage: G.diameter() 7 sage: G.is_distance_regular(True) ([4, 3, 3, 2, 2, 1, 1, None], [None, 1, 1, 2, 2, 3, 3, 4])
REFERENCES:
See [BCN1989] pp. 259-261 or [VDKT2016] p. 25.
-
sage.graphs.generators.distance_regular.
DoublyTruncatedWittGraph
()¶ Return the doubly truncated Witt graph.
This builds the truncated Witt graph, then removes all vertices whose codeword start with a 1.
The graph is distance-regular with intersection array \([7,6,4,4;1,1,1,6]\).
EXAMPLES:
sage: G = graphs.DoublyTruncatedWittGraph() sage: G.is_distance_regular(True) ([7, 6, 4, 4, None], [None, 1, 1, 1, 6])
REFERENCES:
A description and construction of this graph can be found in [BCN1989] p. 368.
-
sage.graphs.generators.distance_regular.
FosterGraph3S6
()¶ Return the Foster graph for \(3.Sym(6)\).
This graph is distance-regular with intersection array \([6, 4, 2, 1; 1, 1, 4, 6]\).
The graph is also distance transitive.
EXAMPLES:
sage: G = graphs.FosterGraph3S6() sage: G.is_distance_regular(True) ([6, 4, 2, 1, None], [None, 1, 1, 4, 6])
REFERENCES:
A description and construction of this graph can be found in [BCN1989] p. 397.
-
sage.graphs.generators.distance_regular.
GrassmannGraph
(q, n, input_e)¶ Return the Grassmann graph with parameters \((q, n, e)\).
This builds the Grassmann graph \(J_q(n,e)\). That is, for a vector space \(V = \mathbb F(q)^n\) the output is the graph on the subspaces of dimension \(e\) where two subspaces are adjancent if their intersection has dimension \(e-1\).
This graph is distance-regular with classical parameters \((\min(e, n-e), q, q, \genfrac {[}{]} {0pt} {} {n-e+1} 1 _q -1)\)
INPUT:
q
– a prime powern, e
– integers withn > e+1
EXAMPLES:
sage: G = graphs.GrassmannGraph(2, 4, 2) sage: G.is_distance_regular(True) ([18, 8, None], [None, 1, 9])
REFERENCES:
See [BCN1989] pp. 268-272 or [VDKT2016] p. 21.
-
sage.graphs.generators.distance_regular.
HalfCube
(n)¶ Return the halved cube in \(n\) dimensions.
The graph is distance-regular with classical parameters \((\lfloor \frac n 2 \rfloor, 1, 2, 2 \lceil \frac n 2 \rceil -1)\).
INPUT:
n
– integer; must be greater than 2
EXAMPLES:
sage: G = graphs.HalfCube(8) sage: G.is_distance_regular(True) ([28, 15, 6, 1, None], [None, 1, 6, 15, 28]) sage: G = graphs.HalfCube(4) sage: G.is_distance_regular(True) ([6, 1, None], [None, 1, 6])
REFERENCES:
See [BCN1989] pp. 264, 265 or [VDKT2016] p. 21. This construction can be found on https://en.wikipedia.org/wiki/Halved_cube_graph#Equivalent_constructions
-
sage.graphs.generators.distance_regular.
HermitianFormsGraph
(n, r)¶ Return the Hermitian froms graph with the given parameters.
We build a graph whose vertices are all
n``x``n
Hermitian matrices overGF(r^2)
. Two vertices are adjacent if the difference of the two vertices has rank 1.This graph is distance-regular with classical parameters \((n, - r, - r - 1, - (- r)^d - 1)\).
INPUT:
n
– integerr
– a prime power
EXAMPLES:
sage: G = graphs.HermitianFormsGraph(2, 2) sage: G.is_distance_regular(True) ([5, 4, None], [None, 1, 2]) sage: G = graphs.HermitianFormsGraph(3, 3) # not tested (2 min) sage: G.order() # not tested (bacuase of the above) 19683
REFERENCES:
See [BCN1989] p. 285 or [VDKT2016] p. 22.
-
sage.graphs.generators.distance_regular.
IvanovIvanovFaradjevGraph
()¶ Return the IvanovIvanovFaradjev graph.
The graph is distance-transitive with automorphism group \(3.M_{22}\).
EXAMPLES:
sage: G = graphs.IvanovIvanovFaradjevGraph() # optional - internet gap_packages sage: G.is_distance_regular(True) # optional - internet gap_packages ([7, 6, 4, 4, 4, 1, 1, 1, None], [None, 1, 1, 1, 2, 4, 4, 6, 7])
REFERENCES:
A description and construction of this graph can be found in [BCN1989] p. 369.
-
sage.graphs.generators.distance_regular.
J2Graph
()¶ Return the distance-transitive graph with automorphism group \(J_2\).
EXAMPLES:
sage: G = graphs.J2Graph() # optional - internet gap_packages sage: G.is_distance_regular(True) # optional - internet gap_packages ([10, 8, 8, 2, None], [None, 1, 1, 4, 5])
REFERENCES:
A description and construction of this graph can be found in [BCN1989] p. 408.
-
sage.graphs.generators.distance_regular.
LargeWittGraph
()¶ Return the large Witt graph.
This is a distance-regular graph with intersection array \([30,28,24;1,3,15]\).
EXAMPLES:
sage: g = graphs.LargeWittGraph() sage: g.is_distance_regular(True) ([30, 28, 24, None], [None, 1, 3, 15])
REFERENCES:
A description of this graph can be found in [BCN1989] p. 366. This construction is taken from http://mathworld.wolfram.com/LargeWittGraph.html
-
sage.graphs.generators.distance_regular.
LeonardGraph
()¶ Return the Leonard graph.
The graph is distance-regular with intersection array \([12, 11, 10, 7; 1, 2, 5, 12]\).
EXAMPLES:
sage: G = graphs.LeonardGraph() sage: G.is_distance_regular(True) ([12, 11, 10, 7, None], [None, 1, 2, 5, 12])
REFERENCES:
For a description of this graph see [BCN1989] p. 371.
-
sage.graphs.generators.distance_regular.
TruncatedWittGraph
()¶ Return the truncated Witt graph.
This builds the large Witt graph, then removes all vertices whose codeword start with a 1.
The graph is distance-regular with intersection array \([15,14,12;1,1,9]\).
EXAMPLES:
sage: G = graphs.TruncatedWittGraph() # long time sage: G.is_distance_regular(True) # long time (due to above) ([15, 14, 12, None], [None, 1, 1, 9])
REFERENCES:
A description and construction of this graph can be found in [BCN1989] p. 367.
-
sage.graphs.generators.distance_regular.
UstimenkoGraph
(m, q)¶ Return the Ustimenko graph with parameters \((m, q)\).
This is the distance 1 or 2 graph of the dual polar graph \(C_{m-1}(q)\). The graph is distance-regular with classical with parameters \((d,q^2, qbinom(3,1,q) -1, qbinom(m+1,1,q) -1)\)
INPUT:
m, q
– integers;q
must be a prime power andm > 1
.
EXAMPLES:
sage: G = graphs.UstimenkoGraph(4, 2) sage: G.is_distance_regular(True) ([70, 32, None], [None, 1, 35])
REFERENCES:
See [BCN1989] p. 279 or [VDKT2016] p. 22.
-
sage.graphs.generators.distance_regular.
cocliques_HoffmannSingleton
()¶ Return the graph obtained from the cocliques of the Hoffmann-Singleton graph.
This is a distance-regular graph with intersection array \([15, 14, 10, 3; 1, 5, 12, 15]\).
EXAMPLES:
sage: G = graphs.cocliques_HoffmannSingleton() sage: G.is_distance_regular(True) ([15, 14, 10, 3, None], [None, 1, 5, 12, 15])
REFERENCES:
The construction of this graph can be found in [BCN1989] p. 392.
-
sage.graphs.generators.distance_regular.
distance_3_doubly_truncated_Golay_code_graph
()¶ Return a distance-regular graph with intersection array \([9, 8, 6, 3; 1, 1, 3, 8]\).
EXAMPLES:
sage: G = graphs.distance_3_doubly_truncated_Golay_code_graph() # long time sage: G.is_distance_regular(True) # long time (due to above) ([9, 8, 6, 3, None], [None, 1, 1, 3, 8])
ALGORITHM:
Compute the binary Golay code and truncate it twice. Compute its coset graph. Take a vertex and compute the set of vertices at distance 3 from the vertex choosen. This set constitutes the set of vertices of our distance-regular graph. Moreover we have an edge \((u,v)\) if the coset graph contains such edge.
REFERENCES:
Description and construction of this graph are taken from [BCN1989] p. 364.
-
sage.graphs.generators.distance_regular.
graph_3O73
()¶ Return the graph related to the group \(3 O(7,3)\).
This graph is distance-regular with intersection array \([117, 80, 24, 1; 1, 12, 80, 117]\).
The graph is also distance transitive with \(3.O(7,3)\) as automorphism group
EXAMPLES:
sage: G = graphs.graph_3O73() # optional - internet gap_packages sage: G.is_distance_regular(True) # optional - internet gap_packages ([117, 80, 24, 1, None], [None, 1, 12, 80, 117])
REFERENCES:
A description and construction of this graph can be found in [BCN1989] p. 400.
-
sage.graphs.generators.distance_regular.
graph_from_GQ_spread
(s, t)¶ Return the point graph of the generalised quandrangle with order \((s, t)\) after removing one of its spreads.
These graphs are antipodal covers of complete graphs and, in particular, distance-regular graphs of diameter 3.
INPUT:
s, t
– integers; order of the generalised quadrangle
EXAMPLES:
sage: from sage.graphs.generators.distance_regular import \ ....: graph_from_GQ_spread sage: G = graph_from_GQ_spread(4, 16) sage: G.is_distance_regular(True) ([64, 60, 1, None], [None, 1, 15, 64])
REFERENCES:
The graphs constructed here follow [BCN1989] pp. 385, 386.
-
sage.graphs.generators.distance_regular.
is_from_GQ_spread
(arr)¶ Return a pair \((s, t)\) if the graph obtained from a GQ of order \((s, t)\) with a spread has the intersection array passed. We also require that such GQ can be built by Sage. If no such pair exists, then return
False
.INPUT:
arr
– list; an intersection array
EXAMPLES:
sage: from sage.graphs.generators.distance_regular import \ ....: is_from_GQ_spread, graph_from_GQ_spread sage: is_from_GQ_spread([125, 120, 1, 1, 24, 125]) (5, 25) sage: G = graph_from_GQ_spread(5, 25) sage: G.is_distance_regular(True) ([125, 120, 1, None], [None, 1, 24, 125])
REFERENCES:
The graphs we are looking for are antipodal covers of complete graphs. See [BCN1989] pp. 385, 386 for a discussion on these particular case.
-
sage.graphs.generators.distance_regular.
locally_GQ42_distance_transitive_graph
()¶ Return the unique amply regular graph with \(\mu = 6\) which is locally a generalised quadrangle.
This graph is distance-regular with intersection array \([45, 32, 12, 1; 1, 6, 32, 45]\).
This graph is also distance-transitive.
EXAMPLES:
sage: G = graphs.locally_GQ42_distance_transitive_graph() # optional - internet gap_packages sage: G.is_distance_regular(True) # optional - internet gap_packages ([45, 32, 12, 1, None], [None, 1, 6, 32, 45])
REFERENCES:
A description of this graph can be found in [BCN1989] p.399. This construction is due to Dima Pasechnik.
-
sage.graphs.generators.distance_regular.
shortened_000_111_extended_binary_Golay_code_graph
()¶ Return a distance-regular graph with intersection array \([21, 20, 16, 9, 2, 1; 1, 2, 3, 16, 20, 21]\).
EXAMPLES:
sage: G = graphs.shortened_000_111_extended_binary_Golay_code_graph() # long time (25 s) sage: G.is_distance_regular(True) # long time ([21, 20, 16, 9, 2, 1, None], [None, 1, 2, 3, 16, 20, 21])
ALGORITHM:
Compute the extended binary Golay code. Compute its subcode whose codewords start with 000 or 111. Remove the first 3 entries from all the codewords from the new linear code and compute its coset graph.
REFERENCES:
Description and construction of this graph can be found in [BCN1989] p. 365.
-
sage.graphs.generators.distance_regular.
shortened_00_11_binary_Golay_code_graph
()¶ Return a distance-regular graph with intersection array \([21, 20, 16, 6, 2, 1; 1, 2, 6, 16, 20, 21]\).
EXAMPLES:
sage: G = graphs.shortened_00_11_binary_Golay_code_graph() # long time (9 s) sage: G.is_distance_regular(True) # long time ([21, 20, 16, 6, 2, 1, None], [None, 1, 2, 6, 16, 20, 21])
ALGORITHM:
Compute the binary Golay code. Compute the subcode whose codewords start with 00 or 11. Remove the first two entries from all codewords of the newly found linear code and compute its coset graph.
REFERENCES:
Description and construction of this graph can be found in [BCN1989] p. 365.
-
sage.graphs.generators.distance_regular.
vanLintSchrijverGraph
()¶ Return the van Lint-Schrijver graph.
The graph is distance-regular with intersection array \([6, 5, 5, 4; 1, 1, 2, 6]\).
EXAMPLES:
sage: G = graphs.vanLintSchrijverGraph() sage: G.is_distance_regular(True) ([6, 5, 5, 4, None], [None, 1, 1, 2, 6])
REFERENCES:
For a description of this graph see [BCN1989] p. 373.