Database of strongly regular graphs

This module manages a database associating to a set of four integers \((v,k,\lambda,\mu)\) a strongly regular graphs with these parameters, when one exists.

Using Andries Brouwer’s database of strongly regular graphs, it can also return non-existence results. Note that some constructions are missing, and that some strongly regular graphs that exist in the database cannot be automatically built by Sage. Help us if you know any. An outline of the implementation can be found in [CP2016].

Note

Any missing/incorrect information in the database must be reported to Andries E. Brouwer directly, in order to have a unique and updated source of information.

REFERENCES:

[BL1984]

Functions

sage.graphs.strongly_regular_db.SRG_100_44_18_20()

Return a \((100, 44, 18, 20)\)-strongly regular graph.

This graph is built as a Cayley graph, using the construction for \(\Delta_1\) with group \(H_3\) presented in Table 8.1 of [JK2003]

EXAMPLES:

sage: from sage.graphs.strongly_regular_db import SRG_100_44_18_20
sage: G = SRG_100_44_18_20()                 # long time
sage: G.is_strongly_regular(parameters=True) # long time
(100, 44, 18, 20)

sage.graphs.strongly_regular_db.SRG_100_45_20_20()

Return a \((100, 45, 20, 20)\)-strongly regular graph.

This graph is built as a Cayley graph, using the construction for \(\Gamma_3\) with group \(H_3\) presented in Table 8.1 of [JK2003].

EXAMPLES:

sage: from sage.graphs.strongly_regular_db import SRG_100_45_20_20
sage: G = SRG_100_45_20_20()              # long time
sage: G.is_strongly_regular(parameters=True) # long time
(100, 45, 20, 20)

sage.graphs.strongly_regular_db.SRG_105_32_4_12()

Return a \((105, 32, 4, 12)\)-strongly regular graph.

The vertices are the flags of the projective plane of order 4. Two flags \((a,A)\) and \((b,B)\) are adjacent if the point \(a\) is on the line \(B\) or the point \(b\) is on the line \(A\), and \(a \neq b\), \(A \neq B\). See Theorem 2.7 in [GS1970], and [Coo2006].

EXAMPLES:

sage: from sage.graphs.strongly_regular_db import SRG_105_32_4_12
sage: G = SRG_105_32_4_12(); G
Aut L(3,4) on flags: Graph on 105 vertices
sage: G.is_strongly_regular(parameters=True)
(105, 32, 4, 12)

sage.graphs.strongly_regular_db.SRG_120_63_30_36()

Return a \((120,63,30,36)\)-strongly regular graph

It is the distance-2 graph of JohnsonGraph(10,3).

EXAMPLES:

sage: from sage.graphs.strongly_regular_db import SRG_120_63_30_36
sage: G =  SRG_120_63_30_36()
sage: G.is_strongly_regular(parameters=True)
(120, 63, 30, 36)

sage.graphs.strongly_regular_db.SRG_120_77_52_44()

Return a \((120,77,52,44)\)-strongly regular graph.

To build this graph, we first build a \(2-(21,7,12)\) design, by removing two points from the WittDesign() on 23 points. We then build the intersection graph of blocks with intersection size 3.

EXAMPLES:

sage: from sage.graphs.strongly_regular_db import SRG_120_77_52_44
sage: G = SRG_120_77_52_44()                 # optional - gap_packages
sage: G.is_strongly_regular(parameters=True) # optional - gap_packages
(120, 77, 52, 44)

sage.graphs.strongly_regular_db.SRG_126_25_8_4()

Return a \((126,25,8,4)\)-strongly regular graph

It is the distance-(1 or 4) graph of JohnsonGraph(9,4).

EXAMPLES:

sage: from sage.graphs.strongly_regular_db import SRG_126_25_8_4
sage: G =  SRG_126_25_8_4()
sage: G.is_strongly_regular(parameters=True)
(126, 25, 8, 4)

sage.graphs.strongly_regular_db.SRG_126_50_13_24()

Return a \((126,50,13,24)\)-strongly regular graph

This graph is a subgraph of SRG_175_72_20_36(). This construction, due to Goethals, is given in §10B.(vii) of [BL1984].

EXAMPLES:

sage: from sage.graphs.strongly_regular_db import SRG_126_50_13_24
sage: G = SRG_126_50_13_24(); G
Goethals graph: Graph on 126 vertices
sage: G.is_strongly_regular(parameters=True)
(126, 50, 13, 24)

sage.graphs.strongly_regular_db.SRG_1288_792_476_504()

Return a \((1288, 792, 476, 504)\)-strongly regular graph.

This graph is built on the words of weight 12 in the BinaryGolayCode(). Two of them are then made adjacent if their symmetric difference has weight 12 (cf [BE1992]).

See also

strongly_regular_from_two_weight_code() – build a strongly regular graph from a two-weight code.

EXAMPLES:

sage: from sage.graphs.strongly_regular_db import SRG_1288_792_476_504
sage: G = SRG_1288_792_476_504()             # long time
sage: G.is_strongly_regular(parameters=True) # long time
(1288, 792, 476, 504)

sage.graphs.strongly_regular_db.SRG_144_39_6_12()

Return a \((144,39,6,12)\)-strongly regular graph.

This graph is obtained as an orbit of length 2808 on sets of cardinality 2 (among 2 such orbits) of the group \(PGL_3(3)\) acting on the (right) cosets of a subgroup of order 39.

EXAMPLES:

sage: from sage.graphs.strongly_regular_db import SRG_144_39_6_12
sage: G = SRG_144_39_6_12()
sage: G.is_strongly_regular(parameters=True)
(144, 39, 6, 12)

sage.graphs.strongly_regular_db.SRG_175_72_20_36()

Return a \((175,72,20,36)\)-strongly regular graph

This graph is obtained from the line graph of HoffmanSingletonGraph(). Setting two vertices to be adjacent if their distance in the line graph is exactly 2 yields the graph. For more information, see 10.B.(iv) in [BL1984] and https://www.win.tue.nl/~aeb/graphs/McL.html.

EXAMPLES:

sage: from sage.graphs.strongly_regular_db import SRG_175_72_20_36
sage: G = SRG_175_72_20_36()
sage: G.is_strongly_regular(parameters=True)
(175, 72, 20, 36)

sage.graphs.strongly_regular_db.SRG_176_105_68_54()

Return a \((176, 105, 68, 54)\)-strongly regular graph.

To build this graph, we first build a \(2-(22,7,16)\) design, by removing one point from the WittDesign() on 23 points. We then build the intersection graph of blocks with intersection size 3. Known as S.7 in [Hub1975].

EXAMPLES:

sage: from sage.graphs.strongly_regular_db import SRG_176_105_68_54
sage: G = SRG_176_105_68_54()                # optional - gap_packages
sage: G.is_strongly_regular(parameters=True) # optional - gap_packages
(176, 105, 68, 54)

sage.graphs.strongly_regular_db.SRG_176_49_12_14()

Return a \((176,49,12,14)\)-strongly regular graph.

This graph is built from the symmetric Higman-Sims design. In [Bro1982], it is explained that there exists an involution \(\sigma\) exchanging the points and blocks of the Higman-Sims design, such that each point is mapped on a block that contains it (i.e. \(\sigma\) is a ‘polarity with all universal points’). The graph is then built by making two vertices \(u,v\) adjacent whenever \(v\in \sigma(u)\).

EXAMPLES:

sage: from sage.graphs.strongly_regular_db import SRG_176_49_12_14
sage: G = SRG_176_49_12_14()                 # optional - gap_packages # long time
sage: G.is_strongly_regular(parameters=True) # optional - gap_packages # long time
(176, 49, 12, 14)

sage.graphs.strongly_regular_db.SRG_176_90_38_54()

Return a \((176,90,38,54)\)-strongly regular graph

This graph is obtained from SRG_175_72_20_36() by attaching a isolated vertex and doing Seidel switching with respect to disjoint union of 18 maximum cliques, following a construction by W.Haemers given in Sect.10.B.(vi) of [BL1984].

EXAMPLES:

sage: from sage.graphs.strongly_regular_db import SRG_176_90_38_54
sage: G = SRG_176_90_38_54(); G
a Seidel switching of Distance graph for distance 2 in : Graph on 176 vertices
sage: G.is_strongly_regular(parameters=True)
(176, 90, 38, 54)

sage.graphs.strongly_regular_db.SRG_196_91_42_42()

Return a \((196,91,42,42)\)-strongly regular graph.

This strongly regular graph is built following the construction provided in Corollary 8.2.27 of [IS2006].

EXAMPLES:

sage: from sage.graphs.strongly_regular_db import SRG_196_91_42_42
sage: G = SRG_196_91_42_42()
sage: G.is_strongly_regular(parameters=True)
(196, 91, 42, 42)

sage.graphs.strongly_regular_db.SRG_210_99_48_45()

Return a strongly regular graph with parameters \((210, 99, 48, 45)\)

This graph is from Example 4.2 in [KPRWZ2010]. One considers the action of the symmetric group \(S_7\) on the 210 digraphs isomorphic to the disjoint union of \(K_1\) and the circulant 6-vertex digraph digraphs.Circulant(6,[1,4]). It has 16 orbitals; the package [FK1991] found a megring of them, explicitly described in [KPRWZ2010], resulting in this graph.

EXAMPLES:

sage: from sage.graphs.strongly_regular_db import SRG_210_99_48_45
sage: g=SRG_210_99_48_45()
sage: g.is_strongly_regular(parameters=True)
(210, 99, 48, 45)

sage.graphs.strongly_regular_db.SRG_220_84_38_28()

Return a \((220, 84, 38, 28)\)-strongly regular graph.

This graph is obtained from the intersection_graph() of a BIBD_45_9_8(). This construction appears in VII.11.2 from [DesignHandbook]

EXAMPLES:

sage: from sage.graphs.strongly_regular_db import SRG_220_84_38_28
sage: g=SRG_220_84_38_28()
sage: g.is_strongly_regular(parameters=True)
(220, 84, 38, 28)

sage.graphs.strongly_regular_db.SRG_243_110_37_60()

Return a \((243, 110, 37, 60)\)-strongly regular graph.

Consider the orthogonal complement of the TernaryGolayCode(), which has 243 words. On them we define a graph, in which two words are adjacent whenever their Hamming distance is 9. This construction appears in [GS1975].

Note

A strongly regular graph with the same parameters is also obtained from the database of 2-weight codes.

EXAMPLES:

sage: from sage.graphs.strongly_regular_db import SRG_243_110_37_60
sage: G = SRG_243_110_37_60()
sage: G.is_strongly_regular(parameters=True)
(243, 110, 37, 60)

sage.graphs.strongly_regular_db.SRG_253_140_87_65()

Return a \((253, 140, 87, 65)\)-strongly regular graph.

To build this graph, we first build the WittDesign() on 23 points which is a \(2-(23,7,21)\) design. We then build the intersection graph of blocks with intersection size 3. Known as S.6 in [Hub1975].

EXAMPLES:

sage: from sage.graphs.strongly_regular_db import SRG_253_140_87_65
sage: G = SRG_253_140_87_65()                # optional - gap_packages
sage: G.is_strongly_regular(parameters=True) # optional - gap_packages
(253, 140, 87, 65)

sage.graphs.strongly_regular_db.SRG_276_140_58_84()

Return a \((276, 140, 58, 84)\)-strongly regular graph.

The graph is built from McLaughlinGraph(), with an added isolated vertex. We then perform a seidel_switching() on a set of 28 disjoint 5-cliques, which exist by cf. [HT1996].

EXAMPLES:

sage: from sage.graphs.strongly_regular_db import SRG_276_140_58_84
sage: g=SRG_276_140_58_84()                  # long time # optional - gap_packages
sage: g.is_strongly_regular(parameters=True) # long time # optional - gap_packages
(276, 140, 58, 84)

sage.graphs.strongly_regular_db.SRG_280_117_44_52()

Return a strongly regular graph with parameters \((280, 117, 44, 52)\).

This graph is built according to a very pretty construction of Mathon and Rosa [MR1985]:

The vertices of the graph \(G\) are all partitions of a set of 9 elements into \(\{\{a,b,c\},\{d,e,f\},\{g,h,i\}\}\). The cross-intersection of two such partitions \(P=\{P_1,P_2,P_3\}\) and \(P'=\{P'_1,P'_2,P'_3\}\) being defined as \(\{P_i \cap P'_j: 1\leq i,j\leq 3\}\), two vertices of \(G\) are set to be adjacent if the cross-intersection of their respective partitions does not contain exactly 7 nonempty sets.

EXAMPLES:

sage: from sage.graphs.strongly_regular_db import SRG_280_117_44_52
sage: g=SRG_280_117_44_52()
sage: g.is_strongly_regular(parameters=True)
(280, 117, 44, 52)

sage.graphs.strongly_regular_db.SRG_280_135_70_60()

Return a strongly regular graph with parameters \((280, 135, 70, 60)\).

This graph is built from the action of \(J_2\) on the cosets of a \(3.PGL(2,9)\)-subgroup.

EXAMPLES:

sage: from sage.graphs.strongly_regular_db import SRG_280_135_70_60
sage: g=SRG_280_135_70_60()                  # long time # optional - internet
sage: g.is_strongly_regular(parameters=True) # long time # optional - internet
(280, 135, 70, 60)

sage.graphs.strongly_regular_db.SRG_416_100_36_20()

Return a \((416,100,36,20)\)-strongly regular graph.

This graph is obtained as an orbit on sets of cardinality 2 (among 2 that exists) of the group \(G_2(4)\). This graph is isomorphic to the subgraph of the from Suzuki Graph induced on the neighbors of a vertex. Known as S.14 in [Hub1975].

EXAMPLES:

sage: from sage.graphs.strongly_regular_db import SRG_416_100_36_20
sage: g = SRG_416_100_36_20()                # long time # optional - internet
sage: g.is_strongly_regular(parameters=True) # long time # optional - internet
(416, 100, 36, 20)

sage.graphs.strongly_regular_db.SRG_560_208_72_80()

Return a \((560,208,72,80)\)-strongly regular graph

This graph is obtained as the union of 4 orbits of sets of cardinality 2 (among the 13 that exist) of the group \(Sz(8)\).

EXAMPLES:

sage: from sage.graphs.strongly_regular_db import SRG_560_208_72_80
sage: g = SRG_560_208_72_80()                # not tested (~2s)
sage: g.is_strongly_regular(parameters=True) # not tested (~2s)
(560, 208, 72, 80)

sage.graphs.strongly_regular_db.SRG_630_85_20_10()

Return a \((630,85,20,10)\)-strongly regular graph

This graph is the line graph of \(pg(5,18,2)\); its point graph is SRG_175_72_20_36(). One selects a subset of 630 maximum cliques in the latter following a construction by W.Haemers given in Sect.10.B.(v) of [BL1984].

EXAMPLES:

sage: from sage.graphs.strongly_regular_db import SRG_630_85_20_10
sage: G = SRG_630_85_20_10()                    # long time
sage: G.is_strongly_regular(parameters=True)    # long time
(630, 85, 20, 10)

sage.graphs.strongly_regular_db.SRG_from_RSHCD(v, k, l, mu, existence=False, check=True)

Return a \((v,k,l,mu)\)-strongly regular graph from a RSHCD

This construction appears in 8.D of [BL1984]. For more information, see regular_symmetric_hadamard_matrix_with_constant_diagonal().

INPUT:

• v,k,l,mu (integers)

• existence (boolean) – whether to return a graph or to test if Sage can build such a graph.

• check (boolean) – whether to check that output is correct before returning it. As this is expected to be useless (but we are cautious guys), you may want to disable it whenever you want speed. Set to True by default.

EXAMPLES:

some graphs

sage: from sage.graphs.strongly_regular_db import SRG_from_RSHCD
sage: SRG_from_RSHCD(784, 0, 14, 38, existence=True)
False
sage: SRG_from_RSHCD(784, 377, 180, 182, existence=True)
True
sage: SRG_from_RSHCD(144, 65, 28, 30)
Graph on 144 vertices

an example with vertex-transitive automorphism group, found during the implementation of the case \(v=324\)

sage: G=SRG_from_RSHCD(324,152,70,72)  # long time
sage: a=G.automorphism_group()         # long time
sage: a.order()                        # long time
2592
sage: len(a.orbits())                  # long time
1

sage.graphs.strongly_regular_db.apparently_feasible_parameters(n)

Return a list of a priori feasible parameters \((v,k,\lambda,\mu)\), with \(0<\mu<k\).

Note that some of those that it returns may also be infeasible for more involved reasons. The condition \(0<\mu<k\) makes sure we skip trivial cases of complete multipartite graphs and their complements.

INPUT:

• n (integer) – return all a-priori feasible tuples \((v,k,\lambda,\mu)\) for \(v<n\)

EXAMPLES:

All sets of parameters with \(v<20\) which pass basic arithmetic tests are feasible:

sage: from sage.graphs.strongly_regular_db import apparently_feasible_parameters
sage: small_feasible = apparently_feasible_parameters(20); small_feasible
{(5, 2, 0, 1),
 (9, 4, 1, 2),
 (10, 3, 0, 1),
 (10, 6, 3, 4),
 (13, 6, 2, 3),
 (15, 6, 1, 3),
 (15, 8, 4, 4),
 (16, 5, 0, 2),
 (16, 6, 2, 2),
 (16, 9, 4, 6),
 (16, 10, 6, 6),
 (17, 8, 3, 4)}
sage: all(graphs.strongly_regular_graph(*x,existence=True) is True for x in small_feasible)
True

But that becomes wrong for \(v<60\) (because of the non-existence of a \((49,16,3,6)\)-strongly regular graph):

sage: small_feasible = apparently_feasible_parameters(60)
sage: all(graphs.strongly_regular_graph(*x,existence=True) is True for x in small_feasible)
False

sage.graphs.strongly_regular_db.eigenmatrix(v, k, l, mu)

Return the first eigenmatrix of a \((v,k,l,mu)\)-strongly regular graph.

The adjacency matrix \(A\) of an s.r.g. commutes with the adjacency matrix \(A'=J-A-I\) of its complement (here \(J\) is all-1 matrix, and \(I\) the identity matrix). Thus, they can be simultaneously diagonalized and so \(A\) and \(A'\) share eigenspaces.

The eigenvalues of \(J\) are \(v\) with multiplicity 1, and 0 with multiplicity \(v-1\). Thus the eigenvalue of \(A'\) corresponding to the 1-dimension \(k\)-eigenspace of \(A\) is \(v-k-1\). Respectively, the eigenvalues of \(A'\) corresponding to \(t\)-eigenspace of \(A\), with \(t\) unequal to \(k\), equals \(-t-1\). The 1st eigenmatrix \(P\) of the C-algebra \(C[A]\) generated by \(A\) encodes this eigenvalue information in its three columns; the 2nd (resp. 3rd) column contains distinct eigenvalues of \(A\) (resp. of \(A'\)), and the 1st column contains the corresponding eigenvalues of \(I\). The matrix \(vP^{-1}\) is called the 2nd eigenvalue matrix of \(C[A]\).

The most interesting feature of \(vP^{-1}\) is that it is the 1st eigenmatrix of the dual of \(C[A]\) if the dual is generated by the adjacency matrix of a strongly regular graph. See [BH2012] and [BI1984] for details.

If the set of parameters is not feasible, or if they correspond to a conference graph, the function returns None. Its output is stable, assuming that the eigenvalues r,s used satisfy r>s; this holds for the current implementation of eigenvalues().

INPUT:

• v,k,l,mu (integers)

EXAMPLES:

Petersen’s graph’s C-algebra does not have a dual coming from an s.r.g.:

sage: from sage.graphs.strongly_regular_db import eigenmatrix
sage: P=eigenmatrix(10,3,0,1); P
[ 1  3  6]
[ 1  1 -2]
[ 1 -2  1]
sage: 10*P^-1
[   1    5    4]
[   1  5/3 -8/3]
[   1 -5/3  2/3]

The line graph of \(K_{3,3}\) is self-dual:

sage: P=eigenmatrix(9,4,1,2); P
[ 1  4  4]
[ 1  1 -2]
[ 1 -2  1]
sage: 9*P^-1
[ 1  4  4]
[ 1  1 -2]
[ 1 -2  1]

A strongly regular graph with a non-isomorphic dual coming from another strongly regular graph:

sage: graphs.strongly_regular_graph(243,220,199,200, existence=True)
True
sage: graphs.strongly_regular_graph(243,110,37,60, existence=True)
True
sage: P=eigenmatrix(243,220,199,200); P
[  1 220  22]
[  1   4  -5]
[  1  -5   4]
sage: 243*P^-1
[  1 110 132]
[  1   2  -3]
[  1 -25  24]
sage: 243*P^-1==eigenmatrix(243,110,37,60)
True

sage.graphs.strongly_regular_db.is_GQqmqp(v, k, l, mu)

Test whether some \(GQ(q-1,q+1)\) or \(GQ(q+1,q-1)\)-graph is \((v,k,\lambda,\mu)\)-srg.

INPUT:

• v,k,l,mu (integers)

OUTPUT:

A tuple t such that t[0](*t[1:]) builds the requested graph if one exists, and None otherwise.

EXAMPLES:

sage: from sage.graphs.strongly_regular_db import is_GQqmqp
sage: t = is_GQqmqp(27,10,1,5); t
(<function AhrensSzekeresGeneralizedQuadrangleGraph at ...>, 3, False)
sage: g = t[0](*t[1:]); g
AS(3); GQ(2, 4): Graph on 27 vertices
sage: t = is_GQqmqp(45,12,3,3); t
(<function AhrensSzekeresGeneralizedQuadrangleGraph at ...>, 3, True)
sage: g = t[0](*t[1:]); g
AS(3)*; GQ(4, 2): Graph on 45 vertices
sage: g.is_strongly_regular(parameters=True)
(45, 12, 3, 3)
sage: t = is_GQqmqp(16,6,2,2); t
(<function T2starGeneralizedQuadrangleGraph at ...>, 2, True)
sage: g = t[0](*t[1:]); g
T2*(O,2)*; GQ(3, 1): Graph on 16 vertices
sage: g.is_strongly_regular(parameters=True)
(16, 6, 2, 2)
sage: t = is_GQqmqp(64,18,2,6); t
(<function T2starGeneralizedQuadrangleGraph at ...>, 4, False)
sage: g = t[0](*t[1:]); g
T2*(O,4); GQ(3, 5): Graph on 64 vertices
sage: g.is_strongly_regular(parameters=True)
(64, 18, 2, 6)

sage.graphs.strongly_regular_db.is_NO_F2(v, k, l, mu)

Test whether some NO^e,perp(2n,2) graph is \((v,k,\lambda,\mu)\)-strongly regular.

For more information, see sage.graphs.graph_generators.GraphGenerators.NonisotropicOrthogonalPolarGraph().

INPUT:

• v,k,l,mu (integers)

OUTPUT:

A tuple t such that t[0](*t[1:]) builds the requested graph if one exists, and None otherwise.

EXAMPLES:

sage: from sage.graphs.strongly_regular_db import is_NO_F2
sage: t = is_NO_F2(10, 3, 0, 1); t
(<function NonisotropicOrthogonalPolarGraph at ...>, 4, 2, '-')
sage: g = t[0](*t[1:]); g
NO^-(4, 2): Graph on 10 vertices
sage: g.is_strongly_regular(parameters=True)
(10, 3, 0, 1)

sage.graphs.strongly_regular_db.is_NO_F3(v, k, l, mu)

Test whether some NO^e,perp(2n,3) graph is \((v,k,\lambda,\mu)\)-strongly regular.

For more information, see sage.graphs.graph_generators.GraphGenerators.NonisotropicOrthogonalPolarGraph().

INPUT:

• v,k,l,mu (integers)

OUTPUT:

A tuple t such that t[0](*t[1:]) builds the requested graph if one exists, and None otherwise.

EXAMPLES:

sage: from sage.graphs.strongly_regular_db import is_NO_F3
sage: t = is_NO_F3(15, 6, 1, 3); t
(<function NonisotropicOrthogonalPolarGraph at ...>, 4, 3, '-')
sage: g = t[0](*t[1:]); g
NO^-(4, 3): Graph on 15 vertices
sage: g.is_strongly_regular(parameters=True)
(15, 6, 1, 3)

sage.graphs.strongly_regular_db.is_NOodd(v, k, l, mu)

Test whether some NO^e(2n+1,q) graph is \((v,k,\lambda,\mu)\)-strongly regular.

Here \(q>2\), for in the case \(q=2\) this graph is complete. For more information, see sage.graphs.graph_generators.GraphGenerators.NonisotropicOrthogonalPolarGraph() and Sect. 7.C of [BL1984].

INPUT:

• v,k,l,mu (integers)

OUTPUT:

A tuple t such that t[0](*t[1:]) builds the requested graph if one exists, and None otherwise.

EXAMPLES:

sage: from sage.graphs.strongly_regular_db import is_NOodd
sage: t = is_NOodd(120, 51, 18, 24); t
(<function NonisotropicOrthogonalPolarGraph at ...>, 5, 4, '-')
sage: g = t[0](*t[1:]); g
NO^-(5, 4): Graph on 120 vertices
sage: g.is_strongly_regular(parameters=True)
(120, 51, 18, 24)

sage.graphs.strongly_regular_db.is_NOperp_F5(v, k, l, mu)

Test whether some NO^e,perp(2n+1,5) graph is \((v,k,\lambda,\mu)\)-strongly regular.

For more information, see sage.graphs.graph_generators.GraphGenerators.NonisotropicOrthogonalPolarGraph() and Sect. 7.D of [BL1984].

INPUT:

• v,k,l,mu (integers)

OUTPUT:

A tuple t such that t[0](*t[1:]) builds the requested graph if one exists, and None otherwise.

EXAMPLES:

sage: from sage.graphs.strongly_regular_db import is_NOperp_F5
sage: t = is_NOperp_F5(10, 3, 0, 1); t
(<function NonisotropicOrthogonalPolarGraph at ...>, 3, 5, '-', 1)
sage: g = t[0](*t[1:]); g
NO^-,perp(3, 5): Graph on 10 vertices
sage: g.is_strongly_regular(parameters=True)
(10, 3, 0, 1)

sage.graphs.strongly_regular_db.is_NU(v, k, l, mu)

Test whether some NU(n,q)-graph, is \((v,k,\lambda,\mu)\)-strongly regular.

Note that n>2; for n=2 there is no s.r.g. For more information, see sage.graphs.graph_generators.GraphGenerators.NonisotropicUnitaryPolarGraph() and series C14 in [Hub1975].

INPUT:

• v,k,l,mu (integers)

OUTPUT:

A tuple t such that t[0](*t[1:]) builds the requested graph if one exists, and None otherwise.

EXAMPLES:

sage: from sage.graphs.strongly_regular_db import is_NU
sage: t = is_NU(40, 27, 18, 18); t
(<function NonisotropicUnitaryPolarGraph at ...>, 4, 2)
sage: g = t[0](*t[1:]); g
NU(4, 2): Graph on 40 vertices
sage: g.is_strongly_regular(parameters=True)
(40, 27, 18, 18)

sage.graphs.strongly_regular_db.is_RSHCD(v, k, l, mu)

Test whether some RSHCD graph is \((v,k,\lambda,\mu)\)-strongly regular.

For more information, see SRG_from_RSHCD().

INPUT:

• v,k,l,mu (integers)

OUTPUT:

A tuple t such that t[0](*t[1:]) builds the requested graph if one exists, and None otherwise.

EXAMPLES:

sage: from sage.graphs.strongly_regular_db import is_RSHCD
sage: t = is_RSHCD(64,27,10,12); t
[<built-in function SRG_from_RSHCD>, 64, 27, 10, 12]
sage: g = t[0](*t[1:]); g
Graph on 64 vertices
sage: g.is_strongly_regular(parameters=True)
(64, 27, 10, 12)

sage.graphs.strongly_regular_db.is_affine_polar(v, k, l, mu)

Test whether some Affine Polar graph is \((v,k,\lambda,\mu)\)-strongly regular.

For more information, see https://www.win.tue.nl/~aeb/graphs/VO.html.

INPUT:

• v,k,l,mu (integers)

OUTPUT:

A tuple t such that t[0](*t[1:]) builds the requested graph if one exists, and None otherwise.

EXAMPLES:

sage: from sage.graphs.strongly_regular_db import is_affine_polar
sage: t = is_affine_polar(81,32,13,12); t
(..., 4, 3)
sage: g = t[0](*t[1:]); g
Affine Polar Graph VO^+(4,3): Graph on 81 vertices
sage: g.is_strongly_regular(parameters=True)
(81, 32, 13, 12)

sage: t = is_affine_polar(5,5,5,5); t

sage.graphs.strongly_regular_db.is_complete_multipartite(v, k, l, mu)

Test whether some complete multipartite graph is \((v,k,\lambda,\mu)\)-strongly regular.

Any complete multipartite graph with parts of the same size is strongly regular.

INPUT:

• v,k,l,mu (integers)

OUTPUT:

A tuple t such that t[0](*t[1:]) builds the requested graph if one exists, and None otherwise.

EXAMPLES:

sage: from sage.graphs.strongly_regular_db import is_complete_multipartite
sage: t = is_complete_multipartite(12,8,4,8); t
(<cyfunction is_complete_multipartite.<locals>.CompleteMultipartiteSRG at ...>,
 3,
 4)
sage: g = t[0](*t[1:]); g
Multipartite Graph with set sizes [4, 4, 4]: Graph on 12 vertices
sage: g.is_strongly_regular(parameters=True)
(12, 8, 4, 8)

sage.graphs.strongly_regular_db.is_cossidente_penttila(v, k, l, mu)

Test whether some CossidentePenttilaGraph graph is \((v,k,\lambda,\mu)\)-strongly regular.

For more information, see CossidentePenttilaGraph().

INPUT:

• v,k,l,mu (integers)

OUTPUT:

A tuple t such that t[0](*t[1:]) builds the requested graph if one exists, and None otherwise.

EXAMPLES:

sage: from sage.graphs.strongly_regular_db import is_cossidente_penttila
sage: t =  is_cossidente_penttila(378, 52, 1, 8); t
(<function CossidentePenttilaGraph at ...>, 5)
sage: g = t[0](*t[1:]); g                      # optional - gap_packages
CossidentePenttila(5): Graph on 378 vertices
sage: g.is_strongly_regular(parameters=True)   # optional - gap_packages
(378, 52, 1, 8)

sage.graphs.strongly_regular_db.is_goethals_seidel(v, k, l, mu)

Test whether some GoethalsSeidelGraph() graph is \((v,k,\lambda,\mu)\)-strongly regular.

INPUT:

• v,k,l,mu (integers)

OUTPUT:

A tuple t such that t[0](*t[1:]) builds the requested graph if one exists, and None otherwise.

EXAMPLES:

sage: from sage.graphs.strongly_regular_db import is_goethals_seidel
sage: t = is_goethals_seidel(28, 15, 6, 10); t
[<function GoethalsSeidelGraph at ...>, 3, 3]
sage: g = t[0](*t[1:]); g
Graph on 28 vertices
sage: g.is_strongly_regular(parameters=True)
(28, 15, 6, 10)

sage: t = is_goethals_seidel(256, 135, 70, 72); t
[<function GoethalsSeidelGraph at ...>, 2, 15]
sage: g = t[0](*t[1:]); g
Graph on 256 vertices
sage: g.is_strongly_regular(parameters=True)
(256, 135, 70, 72)

sage: t = is_goethals_seidel(5,5,5,5); t

sage.graphs.strongly_regular_db.is_haemers(v, k, l, mu)

Test whether some HaemersGraph graph is \((v,k,\lambda,\mu)\)-strongly regular.

For more information, see HaemersGraph().

INPUT:

• v,k,l,mu (integers)

OUTPUT:

A tuple t such that t[0](*t[1:]) builds the requested graph if one exists, and None otherwise.

EXAMPLES:

sage: from sage.graphs.strongly_regular_db import is_haemers
sage: t = is_haemers(96, 19, 2, 4); t
(<function HaemersGraph at ...>, 4)
sage: g = t[0](*t[1:]); g
Haemers(4): Graph on 96 vertices
sage: g.is_strongly_regular(parameters=True)
(96, 19, 2, 4)

sage.graphs.strongly_regular_db.is_johnson(v, k, l, mu)

Test whether some Johnson graph is \((v,k,\lambda,\mu)\)-strongly regular.

INPUT:

• v,k,l,mu (integers)

OUTPUT:

A tuple t such that t[0](*t[1:]) builds the requested graph if one exists, and None otherwise.

EXAMPLES:

sage: from sage.graphs.strongly_regular_db import is_johnson
sage: t = is_johnson(10,6,3,4); t
(..., 5)
sage: g = t[0](*t[1:]); g
Johnson graph with parameters 5,2: Graph on 10 vertices
sage: g.is_strongly_regular(parameters=True)
(10, 6, 3, 4)

sage: t = is_johnson(5,5,5,5); t

sage.graphs.strongly_regular_db.is_mathon_PC_srg(v, k, l, mu)

Test whether some Mathon’s Pseudocyclic s.r.g. is \((v,k,\lambda,\mu)\)-strongly regular.

INPUT:

• v,k,l,mu (integers)

OUTPUT:

A tuple t such that t[0](*t[1:]) builds the requested graph if one exists, and None otherwise.

Todo

The current implementation only gives a subset of all possible graphs that can be obtained using this construction. A full implementation should rely on a database of conference matrices (or, equivalently, on a database of s.r.g.’s with parameters \((4t+1,2t,t-1,t)\). Currently we make an extra assumption that \(4t+1\) is a prime power. The first case where we miss a construction is \(t=11\), where we could (recursively) use the graph for \(t=1\) to construct a graph on 83205 vertices.

EXAMPLES:

sage: from sage.graphs.strongly_regular_db import is_mathon_PC_srg
sage: t = is_mathon_PC_srg(45,22,10,11); t
(..., 1)
sage: g = t[0](*t[1:]); g
Mathon's PC SRG on 45 vertices: Graph on 45 vertices
sage: g.is_strongly_regular(parameters=True)
(45, 22, 10, 11)

sage.graphs.strongly_regular_db.is_muzychuk_S6(v, k, l, mu)

Test whether some Muzychuk S6 graph is (v, k, l, mu)-strongly regular.

Tests whether a MuzychukS6Graph() has parameters (v, k, l, mu).

INPUT:

• v, k, l, mu (integers)

OUTPUT:

A tuple t such that t[0](*t[1:]) builds the required graph if it exists, and None otherwise.

EXAMPLES:

sage: from sage.graphs.strongly_regular_db import is_muzychuk_S6
sage: t = is_muzychuk_S6(378, 116, 34, 36)
sage: G = t[0](*t[1:]); G
Muzychuk S6 graph with parameters (3,3): Graph on 378 vertices
sage: G.is_strongly_regular(parameters=True)
(378, 116, 34, 36)
sage: t = is_muzychuk_S6(5, 5, 5, 5); t

sage.graphs.strongly_regular_db.is_nowhere0_twoweight(v, k, l, mu)

Test whether some graph of nowhere 0 words is \((v,k,\lambda,\mu)\)-strongly regular.

Test whether a Nowhere0WordsTwoWeightCodeGraph() is \((v,k,\lambda,\mu)\)-strongly regular.

INPUT:

• v,k,l,mu (integers)

OUTPUT:

A tuple t such that t[0](*t[1:]) builds the requested graph if the parameters match, and None otherwise.

EXAMPLES:

sage: graphs.strongly_regular_graph(196, 60, 14, 20)
Nowhere0WordsTwoWeightCodeGraph(8): Graph on 196 vertices

sage.graphs.strongly_regular_db.is_orthogonal_array_block_graph(v, k, l, mu)

Test whether some (pseudo)Orthogonal Array graph is \((v,k,\lambda,\mu)\)-strongly regular.

We know how to construct graphs with parameters of an Orthogonal Array (\(OA(m,n)\)), also known as Latin squares graphs \(L_m(n)\), in several cases where no orthogonal array is known, or even in some cases for which they are known not to exist.

Such graphs are usually called pseudo-Latin squares graphs. Namely, Sage can construct a graph with parameters of an \(OA(m,n)\)-graph whenever there exists a skew-Hadamard matrix of order \(n+1\), and \(m=(n+1)/2\) or \(m=(n-1)/2\). The construction in the former case is due to Goethals-Seidel [BL1984], and in the latter case due to Pasechnik [Pas1992].

INPUT:

• v,k,l,mu (integers)

OUTPUT:

A tuple t such that t[0](*t[1:]) builds the requested graph if one exists, and None otherwise.

EXAMPLES:

sage: from sage.graphs.strongly_regular_db import is_orthogonal_array_block_graph
sage: t = is_orthogonal_array_block_graph(64, 35, 18, 20); t
(..., 5, 8)
sage: g = t[0](*t[1:]); g
OA(5,8): Graph on 64 vertices
sage: g.is_strongly_regular(parameters=True)
(64, 35, 18, 20)
sage: t=is_orthogonal_array_block_graph(225,98,43,42); t
(..., 4)
sage: g = t[0](*t[1:]); g
Pasechnik Graph_4: Graph on 225 vertices
sage: g.is_strongly_regular(parameters=True)
(225, 98, 43, 42)
sage: t=is_orthogonal_array_block_graph(225,112,55,56); t
(..., 4)
sage: g = t[0](*t[1:]); g
skewhad^2_4: Graph on 225 vertices
sage: g.is_strongly_regular(parameters=True)
(225, 112, 55, 56)

sage: t = is_orthogonal_array_block_graph(5,5,5,5); t

sage.graphs.strongly_regular_db.is_orthogonal_polar(v, k, l, mu)

Test whether some Orthogonal Polar graph is \((v,k,\lambda,\mu)\)-strongly regular.

For more information, see https://www.win.tue.nl/~aeb/graphs/srghub.html.

INPUT:

• v,k,l,mu (integers)

OUTPUT:

A tuple t such that t[0](*t[1:]) builds the requested graph if one exists, and None otherwise.

EXAMPLES:

sage: from sage.graphs.strongly_regular_db import is_orthogonal_polar
sage: t = is_orthogonal_polar(85, 20, 3, 5); t
(<function OrthogonalPolarGraph at ...>, 5, 4, '')
sage: g = t[0](*t[1:]); g
Orthogonal Polar Graph O(5, 4): Graph on 85 vertices
sage: g.is_strongly_regular(parameters=True)
(85, 20, 3, 5)

sage: t = is_orthogonal_polar(5,5,5,5); t

sage.graphs.strongly_regular_db.is_paley(v, k, l, mu)

Test whether some Paley graph is \((v,k,\lambda,\mu)\)-strongly regular.

INPUT:

• v,k,l,mu (integers)

OUTPUT:

A tuple t such that t[0](*t[1:]) builds the requested graph if one exists, and None otherwise.

EXAMPLES:

sage: from sage.graphs.strongly_regular_db import is_paley
sage: t = is_paley(13,6,2,3); t
(..., 13)
sage: g = t[0](*t[1:]); g
Paley graph with parameter 13: Graph on 13 vertices
sage: g.is_strongly_regular(parameters=True)
(13, 6, 2, 3)
sage: t = is_paley(5,5,5,5); t

sage.graphs.strongly_regular_db.is_polhill(v, k, l, mu)

Test whether some graph from [Pol2009] is \((1024,k,\lambda,\mu)\)-strongly regular.

Note

This function does not actually explore all strongly regular graphs produced in [Pol2009], but only those on 1024 vertices.

John Polhill offered his help if we attempt to write a code to guess, given \((v,k,\lambda,\mu)\), which of his construction must be applied to find the graph.

INPUT:

• v,k,l,mu (integers)

OUTPUT:

A tuple t such that t[0](*t[1:]) builds the requested graph if the parameters match, and None otherwise.

EXAMPLES:

sage: from sage.graphs.strongly_regular_db import is_polhill
sage: t = is_polhill(1024, 231,  38,  56); t
[<cyfunction is_polhill.<locals>.<lambda> at ...>]
sage: g = t[0](*t[1:]); g                    # not tested (too long)
Graph on 1024 vertices
sage: g.is_strongly_regular(parameters=True) # not tested (too long)
(1024, 231, 38, 56)
sage: t = is_polhill(1024, 264,  56,  72); t
[<cyfunction is_polhill.<locals>.<lambda> at ...>]
sage: t = is_polhill(1024, 297,  76,  90); t
[<cyfunction is_polhill.<locals>.<lambda> at ...>]
sage: t = is_polhill(1024, 330,  98, 110); t
[<cyfunction is_polhill.<locals>.<lambda> at ...>]
sage: t = is_polhill(1024, 462, 206, 210); t
[<cyfunction is_polhill.<locals>.<lambda> at ...>]

sage.graphs.strongly_regular_db.is_steiner(v, k, l, mu)

Test whether some Steiner graph is \((v,k,\lambda,\mu)\)-strongly regular.

A Steiner graph is the intersection graph of a Steiner set system. For more information, see https://www.win.tue.nl/~aeb/graphs/S.html.

INPUT:

• v,k,l,mu (integers)

OUTPUT:

A tuple t such that t[0](*t[1:]) builds the requested graph if one exists, and None otherwise.

EXAMPLES:

sage: from sage.graphs.strongly_regular_db import is_steiner
sage: t = is_steiner(26,15,8,9); t
(..., 13, 3)
sage: g = t[0](*t[1:]); g
Intersection Graph: Graph on 26 vertices
sage: g.is_strongly_regular(parameters=True)
(26, 15, 8, 9)

sage: t = is_steiner(5,5,5,5); t

sage.graphs.strongly_regular_db.is_switch_OA_srg(v, k, l, mu)

Test whether some switch \(OA(k,n)+*\) is \((v,k,\lambda,\mu)\)-strongly regular.

The “switch* \(OA(k,n)+*\) graphs appear on Andries Brouwer’s database and are built by adding an isolated vertex to a OrthogonalArrayBlockGraph(), and a Seidel switching a set of disjoint \(n\)-cocliques.

INPUT:

• v,k,l,mu (integers)

OUTPUT:

A tuple t such that t[0](*t[1:]) builds the requested graph if the parameters match, and None otherwise.

EXAMPLES:

sage: graphs.strongly_regular_graph(170, 78, 35, 36) # indirect doctest
Graph on 170 vertices

sage.graphs.strongly_regular_db.is_switch_skewhad(v, k, l, mu)

Test whether some switch skewhad^2+* is \((v,k,\lambda,\mu)\)-strongly regular.

The switch skewhad^2+* graphs appear on Andries Brouwer’s database and are built by adding an isolated vertex to the complement of SquaredSkewHadamardMatrixGraph(), and a Seidel switching a set of disjoint \(n\)-cocliques.

INPUT:

• v,k,l,mu (integers)

OUTPUT:

A tuple t such that t[0](*t[1:]) builds the requested graph if the parameters match, and None otherwise.

EXAMPLES:

sage: graphs.strongly_regular_graph(226, 105, 48, 49)
switch skewhad^2+*_4: Graph on 226 vertices

sage.graphs.strongly_regular_db.is_taylor_twograph_srg(v, k, l, mu)

Test whether some Taylor two-graph SRG is \((v,k,\lambda,\mu)\)-strongly regular.

For more information, see §7E of [BL1984].

INPUT:

• v,k,l,mu (integers)

OUTPUT:

A tuple t such that t[0](*t[1:]) builds the requested graph TaylorTwographSRG if the parameters match, and None otherwise.

EXAMPLES:

sage: from sage.graphs.strongly_regular_db import is_taylor_twograph_srg
sage: t = is_taylor_twograph_srg(28, 15, 6, 10); t
(<function TaylorTwographSRG at ...>, 3)
sage: g = t[0](*t[1:]); g
Taylor two-graph SRG: Graph on 28 vertices
sage: g.is_strongly_regular(parameters=True)
(28, 15, 6, 10)
sage: t = is_taylor_twograph_srg(5,5,5,5); t

sage.graphs.strongly_regular_db.is_twograph_descendant_of_srg(v, k0, l, mu)

Test whether some descendant graph of a s.r.g. is \((v,k_0,\lambda,\mu)\)-s.r.g.

We check whether there can exist \((v+1,k,\lambda^*,\mu^*)\)-s.r.g. \(G\) so that self is a descendant graph of the regular two-graph specified by \(G\). Specifically, we must have that \(v+1=2(2k-\lambda^*-\mu^*)\), and \(k_0=2(k-\mu^*)\), \(\lambda=k+\lambda^*-2\mu^*\), \(\mu=k-\mu^*\), which give 2 independent linear conditions, say \(k-\mu^*=\mu\) and \(\lambda^*-\mu^*=\lambda-\mu\). Further, there is a quadratic relation \(2 k^2-(v+1+4 \mu) k+ 2 v \mu=0\).

If we can construct such \(G\) then we return a function to build a \((v,k_0,\lambda,\mu)\)-s.r.g. For more information, see 10.3 in https://www.win.tue.nl/~aeb/2WF02/spectra.pdf

INPUT:

• v,k0,l,mu (integers)

OUTPUT:

A tuple t such that t[0](*t[1:]) builds the requested graph if one exists and is known, and None otherwise.

EXAMPLES:

sage: from sage.graphs.strongly_regular_db import is_twograph_descendant_of_srg
sage: t = is_twograph_descendant_of_srg(27, 10, 1, 5); t
(<cyfunction is_twograph_descendant_of_srg.<locals>.la at...
sage: g = t[0](*t[1:]); g
descendant of complement(Johnson graph with parameters 8,2) at {0, 1}: Graph on 27 vertices
sage: g.is_strongly_regular(parameters=True)
(27, 10, 1, 5)
sage: t = is_twograph_descendant_of_srg(5,5,5,5); t

sage.graphs.strongly_regular_db.is_unitary_dual_polar(v, k, l, mu)

Test whether some Unitary Dual Polar graph is \((v,k,\lambda,\mu)\)-strongly regular.

This must be the U_5(q) on totally isotropic lines. For more information, see https://www.win.tue.nl/~aeb/graphs/srghub.html.

INPUT:

• v,k,l,mu (integers)

OUTPUT:

A tuple t such that t[0](*t[1:]) builds the requested graph if one exists, and None otherwise.

EXAMPLES:

sage: from sage.graphs.strongly_regular_db import is_unitary_dual_polar
sage: t = is_unitary_dual_polar(297, 40, 7, 5); t
(<function UnitaryDualPolarGraph at ...>, 5, 2)
sage: g = t[0](*t[1:]); g
Unitary Dual Polar Graph DU(5, 2); GQ(8, 4): Graph on 297 vertices
sage: g.is_strongly_regular(parameters=True)
(297, 40, 7, 5)
sage: t = is_unitary_dual_polar(5,5,5,5); t

sage.graphs.strongly_regular_db.is_unitary_polar(v, k, l, mu)

Test whether some Unitary Polar graph is \((v,k,\lambda,\mu)\)-strongly regular.

For more information, see https://www.win.tue.nl/~aeb/graphs/srghub.html.

INPUT:

• v,k,l,mu (integers)

OUTPUT:

A tuple t such that t[0](*t[1:]) builds the requested graph if one exists, and None otherwise.

EXAMPLES:

sage: from sage.graphs.strongly_regular_db import is_unitary_polar
sage: t = is_unitary_polar(45, 12, 3, 3); t
(<function UnitaryPolarGraph at ...>, 4, 2)
sage: g = t[0](*t[1:]); g
Unitary Polar Graph U(4, 2); GQ(4, 2): Graph on 45 vertices
sage: g.is_strongly_regular(parameters=True)
(45, 12, 3, 3)

sage: t = is_unitary_polar(5,5,5,5); t

sage.graphs.strongly_regular_db.latin_squares_graph_parameters(v, k, l, mu)

Check whether (v,k,l,mu)-strongly regular graph has parameters of an \(L_g(n)\) s.r.g.

Also known as pseudo-OA(n,g) case, i.e. s.r.g. with parameters of an OA(n,g)-graph. Return g and n, if they exist. See Sect. 9.1 of [BH2012] for details.

INPUT:

• v,k,l,mu – (integers) parameters of the graph

OUTPUT:

• (g, n) – parameters of an \(L_g(n)\) graph, or \(None\)

sage.graphs.strongly_regular_db.strongly_regular_from_two_intersection_set(M)

Return a strongly regular graph from a 2-intersection set.

A set of points in the projective geometry \(PG(k,q)\) is said to be a 2-intersection set if it intersects every hyperplane in either \(h_1\) or \(h_2\) points, where \(h_1,h_2\in \\NN\).

From a 2-intersection set \(S\) can be defined a strongly-regular graph in the following way:

• Place the points of \(S\) on a hyperplane \(H\) in \(PG(k+1,q)\)

• Define the graph \(G\) on all points of \(PG(k+1,q)\backslash H\)

• Make two points of \(V(G)=PG(k+1,q)\backslash H\) adjacent if the line going through them intersects \(S\)

For more information, see e.g. [CD2013] where this explanation has been taken from.

INPUT:

• \(M\) – a \(|S| \times k\) matrix with entries in \(F_q\) representing the points of the 2-intersection set. We assume that the first non-zero entry of each row is equal to \(1\), that is, they give points in homogeneous coordinates.

The implementation does not check that \(S\) is actually a 2-intersection set.

EXAMPLES:

sage: from sage.graphs.strongly_regular_db import strongly_regular_from_two_intersection_set
sage: S = Matrix([(0,0,1),(0,1,0)] + [(1,x^2,x) for x in GF(4,'b')])
sage: g = strongly_regular_from_two_intersection_set(S); g
two-intersection set in PG(3,4): Graph on 64 vertices
sage: g.is_strongly_regular(parameters=True)
(64, 18, 2, 6)

sage.graphs.strongly_regular_db.strongly_regular_from_two_weight_code(L)

Return a strongly regular graph from a two-weight code.

A code is said to be a two-weight code the weight of its nonzero codewords (i.e. their number of nonzero coordinates) can only be one of two integer values \(w_1,w_2\). It is said to be projective if the minimum weight of the dual code is \(\geq 3\). A strongly regular graph can be built from a two-weight projective code with weights \(w_1,w_2\) (assuming \(w_1<w_2\)) by adding an edge between any two codewords whose difference has weight \(w_1\). For more information, see [LS1981] or [Del1972].

INPUT:

• L – a two-weight linear code, or its generating matrix.

EXAMPLES:

sage: from sage.graphs.strongly_regular_db import strongly_regular_from_two_weight_code
sage: x=("100022021001111",
....:    "010011211122000",
....:    "001021112100011",
....:    "000110120222220")
sage: M = Matrix(GF(3),[list(l) for l in x])
sage: G = strongly_regular_from_two_weight_code(LinearCode(M))
sage: G.is_strongly_regular(parameters=True)
(81, 50, 31, 30)

sage.graphs.strongly_regular_db.strongly_regular_graph(v, k, l, mu=- 1, existence=False, check=True)

Return a \((v,k,\lambda,\mu)\)-strongly regular graph.

This function relies partly on Andries Brouwer’s database of strongly regular graphs. See the documentation of sage.graphs.strongly_regular_db for more information.

INPUT:

• v,k,l,mu (integers) – note that mu, if unspecified, is automatically determined from v,k,l.

• existence (boolean;``False``) – instead of building the graph, return:

  • True – meaning that a \((v,k,\lambda,\mu)\)-strongly regular graph exists.

  • Unknown – meaning that Sage does not know if such a strongly regular graph exists (see sage.misc.unknown).

  • False – meaning that no such strongly regular graph exists.

• check – (boolean) Whether to check that output is correct before returning it. As this is expected to be useless (but we are cautious guys), you may want to disable it whenever you want speed. Set to True by default.

EXAMPLES:

Petersen’s graph from its set of parameters:

sage: graphs.strongly_regular_graph(10,3,0,1,existence=True)
True
sage: graphs.strongly_regular_graph(10,3,0,1)
complement(Johnson graph with parameters 5,2): Graph on 10 vertices

Now without specifying \(\mu\):

sage: graphs.strongly_regular_graph(10,3,0)
complement(Johnson graph with parameters 5,2): Graph on 10 vertices

An obviously infeasible set of parameters:

sage: graphs.strongly_regular_graph(5,5,5,5,existence=True)
False
sage: graphs.strongly_regular_graph(5,5,5,5)
Traceback (most recent call last):
...
ValueError: There exists no (5, 5, 5, 5)-strongly regular graph

An set of parameters proved in a paper to be infeasible:

sage: graphs.strongly_regular_graph(324,57,0,12,existence=True)
False
sage: graphs.strongly_regular_graph(324,57,0,12)
Traceback (most recent call last):
...
EmptySetError: Andries Brouwer's database reports that no (324, 57, 0,
12)-strongly regular graph exists. Comments: <a
href="srgtabrefs.html#GavrilyukMakhnev05">Gavrilyuk & Makhnev</a> ...

A set of parameters unknown to be realizable in Andries Brouwer’s database:

sage: graphs.strongly_regular_graph(324,95,22,30,existence=True)
Unknown
sage: graphs.strongly_regular_graph(324,95,22,30)
Traceback (most recent call last):
...
RuntimeError: Andries Brouwer's database reports that no
(324, 95, 22, 30)-strongly regular graph is known to exist.
Comments:

A large unknown set of parameters (not in Andries Brouwer’s database):

sage: graphs.strongly_regular_graph(1394,175,0,25,existence=True)
Unknown
sage: graphs.strongly_regular_graph(1394,175,0,25)
Traceback (most recent call last):
...
RuntimeError: Sage cannot figure out if a (1394, 175, 0, 25)-strongly
regular graph exists.

Test the Claw bound (see 3.D of [BL1984]):

sage: graphs.strongly_regular_graph(2058,242,91,20,existence=True)
False

sage.graphs.strongly_regular_db.strongly_regular_graph_lazy(v, k, l, mu=- 1, existence=False)

return a promise to build an \((v,k,l,mu)\)-srg

Return a promise to build an \((v,k,l,mu)\)-srg as a tuple \(t\), with \(t[0]\) a function to evaluate on \(*t[1:]\).

Input as in strongly_regular_graph(), although without \(check\).