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()[source]

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                     # needs sage.groups
sage: G.is_strongly_regular(parameters=True)    # long time                     # needs sage.groups
(100, 44, 18, 20)

>>> from sage.all import *
>>> from sage.graphs.strongly_regular_db import SRG_100_44_18_20
>>> G = SRG_100_44_18_20()                    # long time                     # needs sage.groups
>>> G.is_strongly_regular(parameters=True)    # long time                     # needs sage.groups
(100, 44, 18, 20)
sage.graphs.strongly_regular_db.SRG_100_45_20_20()[source]

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                     # needs sage.groups
sage: G.is_strongly_regular(parameters=True)    # long time                     # needs sage.groups
(100, 45, 20, 20)

>>> from sage.all import *
>>> from sage.graphs.strongly_regular_db import SRG_100_45_20_20
>>> G = SRG_100_45_20_20()                    # long time                     # needs sage.groups
>>> G.is_strongly_regular(parameters=True)    # long time                     # needs sage.groups
(100, 45, 20, 20)
sage.graphs.strongly_regular_db.SRG_105_32_4_12()[source]

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                                                  # needs sage.rings.finite_rings
Aut L(3,4) on flags: Graph on 105 vertices
sage: G.is_strongly_regular(parameters=True)                                    # needs sage.rings.finite_rings
(105, 32, 4, 12)

>>> from sage.all import *
>>> from sage.graphs.strongly_regular_db import SRG_105_32_4_12
>>> G = SRG_105_32_4_12(); G                                                  # needs sage.rings.finite_rings
Aut L(3,4) on flags: Graph on 105 vertices
>>> G.is_strongly_regular(parameters=True)                                    # needs sage.rings.finite_rings
(105, 32, 4, 12)
sage.graphs.strongly_regular_db.SRG_120_63_30_36()[source]

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)

>>> from sage.all import *
>>> from sage.graphs.strongly_regular_db import SRG_120_63_30_36
>>> G =  SRG_120_63_30_36()
>>> G.is_strongly_regular(parameters=True)
(120, 63, 30, 36)
sage.graphs.strongly_regular_db.SRG_120_77_52_44()[source]

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_package_design
sage: G.is_strongly_regular(parameters=True)    # optional - gap_package_design
(120, 77, 52, 44)

>>> from sage.all import *
>>> from sage.graphs.strongly_regular_db import SRG_120_77_52_44
>>> G = SRG_120_77_52_44()                    # optional - gap_package_design
>>> G.is_strongly_regular(parameters=True)    # optional - gap_package_design
(120, 77, 52, 44)
sage.graphs.strongly_regular_db.SRG_126_25_8_4()[source]

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)

>>> from sage.all import *
>>> from sage.graphs.strongly_regular_db import SRG_126_25_8_4
>>> G =  SRG_126_25_8_4()
>>> G.is_strongly_regular(parameters=True)
(126, 25, 8, 4)
sage.graphs.strongly_regular_db.SRG_126_50_13_24()[source]

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)

>>> from sage.all import *
>>> from sage.graphs.strongly_regular_db import SRG_126_50_13_24
>>> G = SRG_126_50_13_24(); G
Goethals graph: Graph on 126 vertices
>>> G.is_strongly_regular(parameters=True)
(126, 50, 13, 24)
sage.graphs.strongly_regular_db.SRG_1288_792_476_504()[source]

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                     # needs sage.rings.finite_rings
sage: G.is_strongly_regular(parameters=True)    # long time                     # needs sage.rings.finite_rings
(1288, 792, 476, 504)

>>> from sage.all import *
>>> from sage.graphs.strongly_regular_db import SRG_1288_792_476_504
>>> G = SRG_1288_792_476_504()                # long time                     # needs sage.rings.finite_rings
>>> G.is_strongly_regular(parameters=True)    # long time                     # needs sage.rings.finite_rings
(1288, 792, 476, 504)
sage.graphs.strongly_regular_db.SRG_144_39_6_12()[source]

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()                                                     # needs sage.libs.gap
sage: G.is_strongly_regular(parameters=True)                                    # needs sage.libs.gap
(144, 39, 6, 12)

>>> from sage.all import *
>>> from sage.graphs.strongly_regular_db import SRG_144_39_6_12
>>> G = SRG_144_39_6_12()                                                     # needs sage.libs.gap
>>> G.is_strongly_regular(parameters=True)                                    # needs sage.libs.gap
(144, 39, 6, 12)
sage.graphs.strongly_regular_db.SRG_175_72_20_36()[source]

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)

>>> from sage.all import *
>>> from sage.graphs.strongly_regular_db import SRG_175_72_20_36
>>> G = SRG_175_72_20_36()
>>> G.is_strongly_regular(parameters=True)
(175, 72, 20, 36)
sage.graphs.strongly_regular_db.SRG_176_105_68_54()[source]

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_package_design
sage: G.is_strongly_regular(parameters=True)    # optional - gap_package_design
(176, 105, 68, 54)

>>> from sage.all import *
>>> from sage.graphs.strongly_regular_db import SRG_176_105_68_54
>>> G = SRG_176_105_68_54()                   # optional - gap_package_design
>>> G.is_strongly_regular(parameters=True)    # optional - gap_package_design
(176, 105, 68, 54)
sage.graphs.strongly_regular_db.SRG_176_49_12_14()[source]

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()                    # long time, optional - gap_package_design
sage: G.is_strongly_regular(parameters=True)    # long time, optional - gap_package_design
(176, 49, 12, 14)

>>> from sage.all import *
>>> from sage.graphs.strongly_regular_db import SRG_176_49_12_14
>>> G = SRG_176_49_12_14()                    # long time, optional - gap_package_design
>>> G.is_strongly_regular(parameters=True)    # long time, optional - gap_package_design
(176, 49, 12, 14)
sage.graphs.strongly_regular_db.SRG_176_90_38_54()[source]

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)

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

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)

>>> from sage.all import *
>>> from sage.graphs.strongly_regular_db import SRG_196_91_42_42
>>> G = SRG_196_91_42_42()
>>> G.is_strongly_regular(parameters=True)
(196, 91, 42, 42)
sage.graphs.strongly_regular_db.SRG_210_99_48_45()[source]

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()                                                    # needs sage.libs.gap
sage: g.is_strongly_regular(parameters=True)                                    # needs sage.libs.gap
(210, 99, 48, 45)

>>> from sage.all import *
>>> from sage.graphs.strongly_regular_db import SRG_210_99_48_45
>>> g = SRG_210_99_48_45()                                                    # needs sage.libs.gap
>>> g.is_strongly_regular(parameters=True)                                    # needs sage.libs.gap
(210, 99, 48, 45)
sage.graphs.strongly_regular_db.SRG_220_84_38_28()[source]

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)

>>> from sage.all import *
>>> from sage.graphs.strongly_regular_db import SRG_220_84_38_28
>>> g = SRG_220_84_38_28()
>>> g.is_strongly_regular(parameters=True)
(220, 84, 38, 28)
sage.graphs.strongly_regular_db.SRG_243_110_37_60()[source]

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()                                                   # needs sage.modules sage.rings.finite_rings
sage: G.is_strongly_regular(parameters=True)                                    # needs sage.modules sage.rings.finite_rings
(243, 110, 37, 60)

>>> from sage.all import *
>>> from sage.graphs.strongly_regular_db import SRG_243_110_37_60
>>> G = SRG_243_110_37_60()                                                   # needs sage.modules sage.rings.finite_rings
>>> G.is_strongly_regular(parameters=True)                                    # needs sage.modules sage.rings.finite_rings
(243, 110, 37, 60)
sage.graphs.strongly_regular_db.SRG_253_140_87_65()[source]

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_package_design
sage: G.is_strongly_regular(parameters=True)    # optional - gap_package_design
(253, 140, 87, 65)

>>> from sage.all import *
>>> from sage.graphs.strongly_regular_db import SRG_253_140_87_65
>>> G = SRG_253_140_87_65()                   # optional - gap_package_design
>>> G.is_strongly_regular(parameters=True)    # optional - gap_package_design
(253, 140, 87, 65)
sage.graphs.strongly_regular_db.SRG_276_140_58_84()[source]

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_package_design
sage: g.is_strongly_regular(parameters=True)    # long time, optional - gap_package_design
(276, 140, 58, 84)

>>> from sage.all import *
>>> from sage.graphs.strongly_regular_db import SRG_276_140_58_84
>>> g = SRG_276_140_58_84()                   # long time, optional - gap_package_design
>>> g.is_strongly_regular(parameters=True)    # long time, optional - gap_package_design
(276, 140, 58, 84)
sage.graphs.strongly_regular_db.SRG_280_117_44_52()[source]

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)

>>> from sage.all import *
>>> from sage.graphs.strongly_regular_db import SRG_280_117_44_52
>>> g=SRG_280_117_44_52()
>>> g.is_strongly_regular(parameters=True)
(280, 117, 44, 52)
sage.graphs.strongly_regular_db.SRG_280_135_70_60()[source]

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)

>>> from sage.all import *
>>> from sage.graphs.strongly_regular_db import SRG_280_135_70_60
>>> g=SRG_280_135_70_60()                     # long time, optional - internet
>>> g.is_strongly_regular(parameters=True)    # long time, optional - internet
(280, 135, 70, 60)
sage.graphs.strongly_regular_db.SRG_416_100_36_20()[source]

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, needs sage.libs.gap
sage: g.is_strongly_regular(parameters=True)    # long time, optional - internet, needs sage.libs.gap
(416, 100, 36, 20)

>>> from sage.all import *
>>> from sage.graphs.strongly_regular_db import SRG_416_100_36_20
>>> g = SRG_416_100_36_20()                   # long time, optional - internet, needs sage.libs.gap
>>> g.is_strongly_regular(parameters=True)    # long time, optional - internet, needs sage.libs.gap
(416, 100, 36, 20)
sage.graphs.strongly_regular_db.SRG_560_208_72_80()[source]

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)              # needs sage.libs.gap
sage: g.is_strongly_regular(parameters=True)    # not tested (~2s)              # needs sage.libs.gap
(560, 208, 72, 80)

>>> from sage.all import *
>>> from sage.graphs.strongly_regular_db import SRG_560_208_72_80
>>> g = SRG_560_208_72_80()                   # not tested (~2s)              # needs sage.libs.gap
>>> g.is_strongly_regular(parameters=True)    # not tested (~2s)              # needs sage.libs.gap
(560, 208, 72, 80)
sage.graphs.strongly_regular_db.SRG_630_85_20_10()[source]

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                     # needs sage.groups
sage: G.is_strongly_regular(parameters=True)    # long time                     # needs sage.groups
(630, 85, 20, 10)

>>> from sage.all import *
>>> from sage.graphs.strongly_regular_db import SRG_630_85_20_10
>>> G = SRG_630_85_20_10()                    # long time                     # needs sage.groups
>>> G.is_strongly_regular(parameters=True)    # long time                     # needs sage.groups
(630, 85, 20, 10)
sage.graphs.strongly_regular_db.SRG_from_RSHCD(v, k, l, mu, existence=False, check=True)[source]

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 (default: True); whether to check that output is correct before returning it. As this is expected to be useless, you may want to disable it whenever you want speed.

EXAMPLES:

some graphs

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

>>> from sage.all import *
>>> from sage.graphs.strongly_regular_db import SRG_from_RSHCD
>>> SRG_from_RSHCD(Integer(784), Integer(0), Integer(14), Integer(38), existence=True)                            # needs sage.combinat sage.modules
False
>>> SRG_from_RSHCD(Integer(784), Integer(377), Integer(180), Integer(182), existence=True)                        # needs sage.combinat sage.modules
True
>>> SRG_from_RSHCD(Integer(144), Integer(65), Integer(28), Integer(30))                                           # needs sage.combinat sage.modules
Graph on 144 vertices

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

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

>>> from sage.all import *
>>> # long time, needs sage.combinat sage.modules
>>> G = SRG_from_RSHCD(Integer(324),Integer(152),Integer(70),Integer(72))
>>> a = G.automorphism_group()
>>> a.order()
2592
>>> len(a.orbits())
1
sage.graphs.strongly_regular_db.apparently_feasible_parameters(n)[source]

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              # needs sage.libs.pari
....:     for x in small_feasible)
True

>>> from sage.all import *
>>> from sage.graphs.strongly_regular_db import apparently_feasible_parameters
>>> small_feasible = apparently_feasible_parameters(Integer(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)}
>>> all(graphs.strongly_regular_graph(*x,existence=True) is True              # needs sage.libs.pari
...     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              # needs sage.libs.pari
....:     for x in small_feasible)
False

>>> from sage.all import *
>>> small_feasible = apparently_feasible_parameters(Integer(60))
>>> all(graphs.strongly_regular_graph(*x,existence=True) is True              # needs sage.libs.pari
...     for x in small_feasible)
False
sage.graphs.strongly_regular_db.eigenmatrix(v, k, l, mu)[source]

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                                              # needs sage.modules
[ 1  3  6]
[ 1  1 -2]
[ 1 -2  1]
sage: 10*P^-1                                                                   # needs sage.modules
[   1    5    4]
[   1  5/3 -8/3]
[   1 -5/3  2/3]

>>> from sage.all import *
>>> from sage.graphs.strongly_regular_db import eigenmatrix
>>> P = eigenmatrix(Integer(10),Integer(3),Integer(0),Integer(1)); P                                              # needs sage.modules
[ 1  3  6]
[ 1  1 -2]
[ 1 -2  1]
>>> Integer(10)*P**-Integer(1)                                                                   # needs sage.modules
[   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                                               # needs sage.modules
[ 1  4  4]
[ 1  1 -2]
[ 1 -2  1]
sage: 9*P^-1                                                                    # needs sage.modules
[ 1  4  4]
[ 1  1 -2]
[ 1 -2  1]

>>> from sage.all import *
>>> P = eigenmatrix(Integer(9),Integer(4),Integer(1),Integer(2)); P                                               # needs sage.modules
[ 1  4  4]
[ 1  1 -2]
[ 1 -2  1]
>>> Integer(9)*P**-Integer(1)                                                                    # needs sage.modules
[ 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: # needs sage.modules
sage: graphs.strongly_regular_graph(243,220,199,200, existence=True)            # needs sage.combinat
True
sage: graphs.strongly_regular_graph(243,110,37,60, existence=True)              # needs sage.combinat
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

>>> from sage.all import *
>>> # needs sage.modules
>>> graphs.strongly_regular_graph(Integer(243),Integer(220),Integer(199),Integer(200), existence=True)            # needs sage.combinat
True
>>> graphs.strongly_regular_graph(Integer(243),Integer(110),Integer(37),Integer(60), existence=True)              # needs sage.combinat
True
>>> P = eigenmatrix(Integer(243),Integer(220),Integer(199),Integer(200)); P
[  1 220  22]
[  1   4  -5]
[  1  -5   4]
>>> Integer(243)*P**-Integer(1)
[  1 110 132]
[  1   2  -3]
[  1 -25  24]
>>> Integer(243)*P**-Integer(1)==eigenmatrix(Integer(243),Integer(110),Integer(37),Integer(60))
True
sage.graphs.strongly_regular_db.is_GQqmqp(k, l, mu)[source]

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: # needs sage.libs.pari
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)

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

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                                              # needs sage.libs.pari
(<function NonisotropicOrthogonalPolarGraph at ...>, 4, 2, '-')
sage: g = t[0](*t[1:]); g                                                       # needs sage.libs.pari
NO^-(4, 2): Graph on 10 vertices
sage: g.is_strongly_regular(parameters=True)                                    # needs sage.libs.pari
(10, 3, 0, 1)

>>> from sage.all import *
>>> from sage.graphs.strongly_regular_db import is_NO_F2
>>> t = is_NO_F2(Integer(10), Integer(3), Integer(0), Integer(1)); t                                              # needs sage.libs.pari
(<function NonisotropicOrthogonalPolarGraph at ...>, 4, 2, '-')
>>> g = t[Integer(0)](*t[Integer(1):]); g                                                       # needs sage.libs.pari
NO^-(4, 2): Graph on 10 vertices
>>> g.is_strongly_regular(parameters=True)                                    # needs sage.libs.pari
(10, 3, 0, 1)
sage.graphs.strongly_regular_db.is_NO_F3(k, l, mu)[source]

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                                              # needs sage.libs.pari
(<function NonisotropicOrthogonalPolarGraph at ...>, 4, 3, '-')
sage: g = t[0](*t[1:]); g                                                       # needs sage.libs.pari
NO^-(4, 3): Graph on 15 vertices
sage: g.is_strongly_regular(parameters=True)                                    # needs sage.libs.pari
(15, 6, 1, 3)

>>> from sage.all import *
>>> from sage.graphs.strongly_regular_db import is_NO_F3
>>> t = is_NO_F3(Integer(15), Integer(6), Integer(1), Integer(3)); t                                              # needs sage.libs.pari
(<function NonisotropicOrthogonalPolarGraph at ...>, 4, 3, '-')
>>> g = t[Integer(0)](*t[Integer(1):]); g                                                       # needs sage.libs.pari
NO^-(4, 3): Graph on 15 vertices
>>> g.is_strongly_regular(parameters=True)                                    # needs sage.libs.pari
(15, 6, 1, 3)
sage.graphs.strongly_regular_db.is_NOodd(k, l, mu)[source]

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                                          # needs sage.libs.pari
(<function NonisotropicOrthogonalPolarGraph at ...>, 5, 4, '-')
sage: g = t[0](*t[1:]); g                                                       # needs sage.libs.pari
NO^-(5, 4): Graph on 120 vertices
sage: g.is_strongly_regular(parameters=True)                                    # needs sage.libs.pari
(120, 51, 18, 24)

>>> from sage.all import *
>>> from sage.graphs.strongly_regular_db import is_NOodd
>>> t = is_NOodd(Integer(120), Integer(51), Integer(18), Integer(24)); t                                          # needs sage.libs.pari
(<function NonisotropicOrthogonalPolarGraph at ...>, 5, 4, '-')
>>> g = t[Integer(0)](*t[Integer(1):]); g                                                       # needs sage.libs.pari
NO^-(5, 4): Graph on 120 vertices
>>> g.is_strongly_regular(parameters=True)                                    # needs sage.libs.pari
(120, 51, 18, 24)
sage.graphs.strongly_regular_db.is_NOperp_F5(k, l, mu)[source]

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                                          # needs sage.libs.pari
(<function NonisotropicOrthogonalPolarGraph at ...>, 3, 5, '-', 1)
sage: g = t[0](*t[1:]); g                                                       # needs sage.libs.pari
NO^-,perp(3, 5): Graph on 10 vertices
sage: g.is_strongly_regular(parameters=True)                                    # needs sage.libs.pari
(10, 3, 0, 1)

>>> from sage.all import *
>>> from sage.graphs.strongly_regular_db import is_NOperp_F5
>>> t = is_NOperp_F5(Integer(10), Integer(3), Integer(0), Integer(1)); t                                          # needs sage.libs.pari
(<function NonisotropicOrthogonalPolarGraph at ...>, 3, 5, '-', 1)
>>> g = t[Integer(0)](*t[Integer(1):]); g                                                       # needs sage.libs.pari
NO^-,perp(3, 5): Graph on 10 vertices
>>> g.is_strongly_regular(parameters=True)                                    # needs sage.libs.pari
(10, 3, 0, 1)
sage.graphs.strongly_regular_db.is_NU(k, l, mu)[source]

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                                              # needs sage.libs.pari
(<function NonisotropicUnitaryPolarGraph at ...>, 4, 2)
sage: g = t[0](*t[1:]); g                                                       # needs sage.libs.pari
NU(4, 2): Graph on 40 vertices
sage: g.is_strongly_regular(parameters=True)                                    # needs sage.libs.pari
(40, 27, 18, 18)

>>> from sage.all import *
>>> from sage.graphs.strongly_regular_db import is_NU
>>> t = is_NU(Integer(40), Integer(27), Integer(18), Integer(18)); t                                              # needs sage.libs.pari
(<function NonisotropicUnitaryPolarGraph at ...>, 4, 2)
>>> g = t[Integer(0)](*t[Integer(1):]); g                                                       # needs sage.libs.pari
NU(4, 2): Graph on 40 vertices
>>> g.is_strongly_regular(parameters=True)                                    # needs sage.libs.pari
(40, 27, 18, 18)
sage.graphs.strongly_regular_db.is_RSHCD(v, k, l, mu)[source]

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                                              # needs sage.combinat sage.modules
[<built-in function SRG_from_RSHCD>, 64, 27, 10, 12]
sage: g = t[0](*t[1:]); g                                                       # needs sage.combinat sage.modules
Graph on 64 vertices
sage: g.is_strongly_regular(parameters=True)                                    # needs sage.combinat sage.modules
(64, 27, 10, 12)

>>> from sage.all import *
>>> from sage.graphs.strongly_regular_db import is_RSHCD
>>> t = is_RSHCD(Integer(64),Integer(27),Integer(10),Integer(12)); t                                              # needs sage.combinat sage.modules
[<built-in function SRG_from_RSHCD>, 64, 27, 10, 12]
>>> g = t[Integer(0)](*t[Integer(1):]); g                                                       # needs sage.combinat sage.modules
Graph on 64 vertices
>>> g.is_strongly_regular(parameters=True)                                    # needs sage.combinat sage.modules
(64, 27, 10, 12)
sage.graphs.strongly_regular_db.is_affine_polar(k, l, mu)[source]

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                                       # needs sage.rings.finite_rings
(..., 4, 3)
sage: g = t[0](*t[1:]); g                                                       # needs sage.rings.finite_rings
Affine Polar Graph VO^+(4,3): Graph on 81 vertices
sage: g.is_strongly_regular(parameters=True)                                    # needs sage.rings.finite_rings
(81, 32, 13, 12)

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

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

>>> t = is_affine_polar(Integer(5),Integer(5),Integer(5),Integer(5)); t
sage.graphs.strongly_regular_db.is_complete_multipartite(k, l, mu)[source]

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)

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

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                             # needs sage.libs.pari
(<function CossidentePenttilaGraph at ...>, 5)
sage: g = t[0](*t[1:]); g                       # optional - gap_package_design, needs sage.libs.pari
CossidentePenttila(5): Graph on 378 vertices
sage: g.is_strongly_regular(parameters=True)    # optional - gap_package_design, needs sage.libs.pari
(378, 52, 1, 8)

>>> from sage.all import *
>>> from sage.graphs.strongly_regular_db import is_cossidente_penttila
>>> t =  is_cossidente_penttila(Integer(378), Integer(52), Integer(1), Integer(8)); t                             # needs sage.libs.pari
(<function CossidentePenttilaGraph at ...>, 5)
>>> g = t[Integer(0)](*t[Integer(1):]); g                       # optional - gap_package_design, needs sage.libs.pari
CossidentePenttila(5): Graph on 378 vertices
>>> g.is_strongly_regular(parameters=True)    # optional - gap_package_design, needs sage.libs.pari
(378, 52, 1, 8)
sage.graphs.strongly_regular_db.is_goethals_seidel(k, l, mu)[source]

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                                  # needs sage.combinat sage.modules
[<function GoethalsSeidelGraph at ...>, 3, 3]
sage: g = t[0](*t[1:]); g                                                       # needs sage.combinat sage.modules
Graph on 28 vertices
sage: g.is_strongly_regular(parameters=True)                                    # needs sage.combinat sage.modules
(28, 15, 6, 10)

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

sage: t = is_goethals_seidel(5,5,5,5); t                                        # needs sage.combinat sage.modules

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

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

>>> t = is_goethals_seidel(Integer(5),Integer(5),Integer(5),Integer(5)); t                                        # needs sage.combinat sage.modules
sage.graphs.strongly_regular_db.is_haemers(k, l, mu)[source]

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                                           # needs sage.libs.pari
(<function HaemersGraph at ...>, 4)
sage: g = t[0](*t[1:]); g                                                       # needs sage.libs.pari
Haemers(4): Graph on 96 vertices
sage: g.is_strongly_regular(parameters=True)                                    # needs sage.libs.pari
(96, 19, 2, 4)

>>> from sage.all import *
>>> from sage.graphs.strongly_regular_db import is_haemers
>>> t = is_haemers(Integer(96), Integer(19), Integer(2), Integer(4)); t                                           # needs sage.libs.pari
(<function HaemersGraph at ...>, 4)
>>> g = t[Integer(0)](*t[Integer(1):]); g                                                       # needs sage.libs.pari
Haemers(4): Graph on 96 vertices
>>> g.is_strongly_regular(parameters=True)                                    # needs sage.libs.pari
(96, 19, 2, 4)
sage.graphs.strongly_regular_db.is_johnson(k, l, mu)[source]

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

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

>>> t = is_johnson(Integer(5),Integer(5),Integer(5),Integer(5)); t
sage.graphs.strongly_regular_db.is_mathon_PC_srg(k, l, mu)[source]

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                                      # needs sage.libs.pari
(..., 1)
sage: g = t[0](*t[1:]); g                                                       # needs sage.libs.pari
Mathon's PC SRG on 45 vertices: Graph on 45 vertices
sage: g.is_strongly_regular(parameters=True)                                    # needs sage.libs.pari
(45, 22, 10, 11)

>>> from sage.all import *
>>> from sage.graphs.strongly_regular_db import is_mathon_PC_srg
>>> t = is_mathon_PC_srg(Integer(45),Integer(22),Integer(10),Integer(11)); t                                      # needs sage.libs.pari
(..., 1)
>>> g = t[Integer(0)](*t[Integer(1):]); g                                                       # needs sage.libs.pari
Mathon's PC SRG on 45 vertices: Graph on 45 vertices
>>> g.is_strongly_regular(parameters=True)                                    # needs sage.libs.pari
(45, 22, 10, 11)
sage.graphs.strongly_regular_db.is_muzychuk_S6(k, l, mu)[source]

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: # needs sage.libs.pari
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

>>> from sage.all import *
>>> # needs sage.libs.pari
>>> from sage.graphs.strongly_regular_db import is_muzychuk_S6
>>> t = is_muzychuk_S6(Integer(378), Integer(116), Integer(34), Integer(36))
>>> G = t[Integer(0)](*t[Integer(1):]); G
Muzychuk S6 graph with parameters (3,3): Graph on 378 vertices
>>> G.is_strongly_regular(parameters=True)
(378, 116, 34, 36)
>>> t = is_muzychuk_S6(Integer(5), Integer(5), Integer(5), Integer(5)); t
sage.graphs.strongly_regular_db.is_nowhere0_twoweight(v, k, l, mu)[source]

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)                            # needs sage.combinat sage.modules
Nowhere0WordsTwoWeightCodeGraph(8): Graph on 196 vertices

>>> from sage.all import *
>>> graphs.strongly_regular_graph(Integer(196), Integer(60), Integer(14), Integer(20))                            # needs sage.combinat sage.modules
Nowhere0WordsTwoWeightCodeGraph(8): Graph on 196 vertices
sage.graphs.strongly_regular_db.is_orthogonal_array_block_graph(k, l, mu)[source]

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: # needs sage.combinat sage.modules
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                           # needs sage.combinat sage.modules

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

>>> t = is_orthogonal_array_block_graph(Integer(5),Integer(5),Integer(5),Integer(5)); t                           # needs sage.combinat sage.modules
sage.graphs.strongly_regular_db.is_orthogonal_polar(k, l, mu)[source]

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                                                       # needs sage.rings.finite_rings
Orthogonal Polar Graph O(5, 4): Graph on 85 vertices
sage: g.is_strongly_regular(parameters=True)                                    # needs sage.rings.finite_rings
(85, 20, 3, 5)

sage: t = is_orthogonal_polar(5,5,5,5); t                                       # needs sage.rings.finite_rings

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

>>> t = is_orthogonal_polar(Integer(5),Integer(5),Integer(5),Integer(5)); t                                       # needs sage.rings.finite_rings
sage.graphs.strongly_regular_db.is_paley(k, l, mu)[source]

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                                                       # needs sage.rings.finite_rings
Paley graph with parameter 13: Graph on 13 vertices
sage: g.is_strongly_regular(parameters=True)                                    # needs sage.rings.finite_rings
(13, 6, 2, 3)
sage: t = is_paley(5,5,5,5); t

>>> from sage.all import *
>>> from sage.graphs.strongly_regular_db import is_paley
>>> t = is_paley(Integer(13),Integer(6),Integer(2),Integer(3)); t
(..., 13)
>>> g = t[Integer(0)](*t[Integer(1):]); g                                                       # needs sage.rings.finite_rings
Paley graph with parameter 13: Graph on 13 vertices
>>> g.is_strongly_regular(parameters=True)                                    # needs sage.rings.finite_rings
(13, 6, 2, 3)
>>> t = is_paley(Integer(5),Integer(5),Integer(5),Integer(5)); t
sage.graphs.strongly_regular_db.is_polhill(k, l, mu)[source]

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: # needs sage.rings.finite_rings
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 ...>]

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

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

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

>>> t = is_steiner(Integer(5),Integer(5),Integer(5),Integer(5)); t
sage.graphs.strongly_regular_db.is_switch_OA_srg(v, k, l, mu)[source]

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        # needs sage.combinat sage.modules
Graph on 170 vertices

>>> from sage.all import *
>>> graphs.strongly_regular_graph(Integer(170), Integer(78), Integer(35), Integer(36))  # indirect doctest        # needs sage.combinat sage.modules
Graph on 170 vertices
sage.graphs.strongly_regular_db.is_switch_skewhad(v, k, l, mu)[source]

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)                           # needs sage.combinat sage.modules
switch skewhad^2+*_4: Graph on 226 vertices

>>> from sage.all import *
>>> graphs.strongly_regular_graph(Integer(226), Integer(105), Integer(48), Integer(49))                           # needs sage.combinat sage.modules
switch skewhad^2+*_4: Graph on 226 vertices
sage.graphs.strongly_regular_db.is_taylor_twograph_srg(k, l, mu)[source]

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: # needs sage.libs.pari
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

>>> from sage.all import *
>>> # needs sage.libs.pari
>>> from sage.graphs.strongly_regular_db import is_taylor_twograph_srg
>>> t = is_taylor_twograph_srg(Integer(28), Integer(15), Integer(6), Integer(10)); t
(<function TaylorTwographSRG at ...>, 3)
>>> g = t[Integer(0)](*t[Integer(1):]); g
Taylor two-graph SRG: Graph on 28 vertices
>>> g.is_strongly_regular(parameters=True)
(28, 15, 6, 10)
>>> t = is_taylor_twograph_srg(Integer(5),Integer(5),Integer(5),Integer(5)); t
sage.graphs.strongly_regular_db.is_twograph_descendant_of_srg(k0, l, mu)[source]

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                        # needs sage.rings.finite_rings
(<cyfunction is_twograph_descendant_of_srg.<locals>.la at...
sage: g = t[0](*t[1:]); g                                                       # needs sage.rings.finite_rings
descendant of complement(Johnson graph with parameters 8,2) at {0, 1}: Graph on 27 vertices
sage: g.is_strongly_regular(parameters=True)                                    # needs sage.rings.finite_rings
(27, 10, 1, 5)
sage: t = is_twograph_descendant_of_srg(5,5,5,5); t

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

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: # needs sage.libs.pari
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

>>> from sage.all import *
>>> # needs sage.libs.pari
>>> from sage.graphs.strongly_regular_db import is_unitary_dual_polar
>>> t = is_unitary_dual_polar(Integer(297), Integer(40), Integer(7), Integer(5)); t
(<function UnitaryDualPolarGraph at ...>, 5, 2)
>>> g = t[Integer(0)](*t[Integer(1):]); g
Unitary Dual Polar Graph DU(5, 2); GQ(8, 4): Graph on 297 vertices
>>> g.is_strongly_regular(parameters=True)
(297, 40, 7, 5)
>>> t = is_unitary_dual_polar(Integer(5),Integer(5),Integer(5),Integer(5)); t
sage.graphs.strongly_regular_db.is_unitary_polar(k, l, mu)[source]

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                                     # needs sage.libs.pari
(<function UnitaryPolarGraph at ...>, 4, 2)
sage: g = t[0](*t[1:]); g                                                       # needs sage.libs.pari
Unitary Polar Graph U(4, 2); GQ(4, 2): Graph on 45 vertices
sage: g.is_strongly_regular(parameters=True)                                    # needs sage.libs.pari
(45, 12, 3, 3)

sage: t = is_unitary_polar(5,5,5,5); t                                          # needs sage.libs.pari

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

>>> t = is_unitary_polar(Integer(5),Integer(5),Integer(5),Integer(5)); t                                          # needs sage.libs.pari
sage.graphs.strongly_regular_db.latin_squares_graph_parameters(v, k, l, mu)[source]

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 – - (integrs) 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)[source]

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 nonzero 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')])            # needs sage.modules sage.rings.finite_rings
sage: g = strongly_regular_from_two_intersection_set(S); g                      # needs sage.modules sage.rings.finite_rings
two-intersection set in PG(3,4): Graph on 64 vertices
sage: g.is_strongly_regular(parameters=True)                                    # needs sage.modules sage.rings.finite_rings
(64, 18, 2, 6)

>>> from sage.all import *
>>> from sage.graphs.strongly_regular_db import strongly_regular_from_two_intersection_set
>>> S = Matrix([(Integer(0),Integer(0),Integer(1)),(Integer(0),Integer(1),Integer(0))] + [(Integer(1),x**Integer(2),x) for x in GF(Integer(4),'b')])            # needs sage.modules sage.rings.finite_rings
>>> g = strongly_regular_from_two_intersection_set(S); g                      # needs sage.modules sage.rings.finite_rings
two-intersection set in PG(3,4): Graph on 64 vertices
>>> g.is_strongly_regular(parameters=True)                                    # needs sage.modules sage.rings.finite_rings
(64, 18, 2, 6)
sage.graphs.strongly_regular_db.strongly_regular_from_two_weight_code(L)[source]

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])                                    # needs sage.modules sage.rings.finite_rings
sage: G = strongly_regular_from_two_weight_code(LinearCode(M))                  # needs sage.modules sage.rings.finite_rings
sage: G.is_strongly_regular(parameters=True)                                    # needs sage.modules sage.rings.finite_rings
(81, 50, 31, 30)

>>> from sage.all import *
>>> from sage.graphs.strongly_regular_db import strongly_regular_from_two_weight_code
>>> x = ("100022021001111",
...      "010011211122000",
...      "001021112100011",
...      "000110120222220")
>>> M = Matrix(GF(Integer(3)),[list(l) for l in x])                                    # needs sage.modules sage.rings.finite_rings
>>> G = strongly_regular_from_two_weight_code(LinearCode(M))                  # needs sage.modules sage.rings.finite_rings
>>> G.is_strongly_regular(parameters=True)                                    # needs sage.modules sage.rings.finite_rings
(81, 50, 31, 30)
sage.graphs.strongly_regular_db.strongly_regular_graph(v, k, l, mu=-1, existence=False, check=True)[source]

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 (default: True); whether to check that output is correct before returning it. As this is expected to be useless, you may want to disable it whenever you want speed.

EXAMPLES:

Petersen’s graph from its set of parameters:

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

>>> from sage.all import *
>>> graphs.strongly_regular_graph(Integer(10),Integer(3),Integer(0),Integer(1),existence=True)                    # needs sage.libs.pari
True
>>> graphs.strongly_regular_graph(Integer(10),Integer(3),Integer(0),Integer(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

>>> from sage.all import *
>>> graphs.strongly_regular_graph(Integer(10),Integer(3),Integer(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

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

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

sage: graphs.strongly_regular_graph(324,57,0,12,existence=True)                 # needs sage.combinat sage.modules
False
sage: graphs.strongly_regular_graph(324,57,0,12)                                # needs sage.combinat sage.modules
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> ...

>>> from sage.all import *
>>> graphs.strongly_regular_graph(Integer(324),Integer(57),Integer(0),Integer(12),existence=True)                 # needs sage.combinat sage.modules
False
>>> graphs.strongly_regular_graph(Integer(324),Integer(57),Integer(0),Integer(12))                                # needs sage.combinat sage.modules
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)                # needs sage.combinat
Unknown
sage: graphs.strongly_regular_graph(324,95,22,30)                               # needs sage.combinat
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:

>>> from sage.all import *
>>> graphs.strongly_regular_graph(Integer(324),Integer(95),Integer(22),Integer(30),existence=True)                # needs sage.combinat
Unknown
>>> graphs.strongly_regular_graph(Integer(324),Integer(95),Integer(22),Integer(30))                               # needs sage.combinat
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)               # needs sage.combinat
Unknown
sage: graphs.strongly_regular_graph(1394,175,0,25)                              # needs sage.combinat
Traceback (most recent call last):
...
RuntimeError: Sage cannot figure out if a (1394, 175, 0, 25)-strongly
regular graph exists.

>>> from sage.all import *
>>> graphs.strongly_regular_graph(Integer(1394),Integer(175),Integer(0),Integer(25),existence=True)               # needs sage.combinat
Unknown
>>> graphs.strongly_regular_graph(Integer(1394),Integer(175),Integer(0),Integer(25))                              # needs sage.combinat
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

>>> from sage.all import *
>>> graphs.strongly_regular_graph(Integer(2058),Integer(242),Integer(91),Integer(20),existence=True)
False
sage.graphs.strongly_regular_db.strongly_regular_graph_lazy(v, k, l, mu=-1, existence=False)[source]

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\).