Static dense graphs

Static dense graphs

This module gathers everything which is related to static dense graphs, i.e. :

  • The vertices are integer from \(0\) to \(n-1\)
  • No labels on vertices/edges
  • No multiple edges
  • No addition/removal of vertices

This being said, it is technically possible to add/remove edges. The data structure does not mind at all.

It is all based on the binary matrix data structure described in misc/binary_matrix.pxi, which is almost a copy of the bitset data structure. The only difference is that it differentiates the rows (the vertices) instead of storing the whole data in a long bitset, and we can use that.


Cython functions

dense_graph_init Fills a binary matrix with the information of a (di)graph.

Python functions

is_strongly_regular() Tests if a graph is strongly regular


sage.graphs.base.static_dense_graph.is_strongly_regular(g, parameters=False)

Tests whether self is strongly regular.

A graph \(G\) is said to be strongly regular with parameters \((n, k, \lambda, \mu)\) if and only if:

  • \(G\) has \(n\) vertices.
  • \(G\) is \(k\)-regular.
  • Any two adjacent vertices of \(G\) have \(\lambda\) common neighbors.
  • Any two non-adjacent vertices of \(G\) have \(\mu\) common neighbors.

By convention, the complete graphs, the graphs with no edges and the empty graph are not strongly regular.

See Wikipedia article Strongly regular graph


  • parameters (boolean) – whether to return the quadruple \((n, k,\lambda,\mu)\). If parameters = False (default), this method only returns True and False answers. If parameters=True, the True answers are replaced by quadruples \((n, k,\lambda,\mu)\). See definition above.


Petersen’s graph is strongly regular:

sage: g = graphs.PetersenGraph()
sage: g.is_strongly_regular()
sage: g.is_strongly_regular(parameters = True)
(10, 3, 0, 1)

And Clebsch’s graph is too:

sage: g = graphs.ClebschGraph()
sage: g.is_strongly_regular()
sage: g.is_strongly_regular(parameters = True)
(16, 5, 0, 2)

But Chvatal’s graph is not:

sage: g = graphs.ChvatalGraph()
sage: g.is_strongly_regular()

Complete graphs are not strongly regular. (trac ticket #14297)

sage: g = graphs.CompleteGraph(5)
sage: g.is_strongly_regular()

Completements of complete graphs are not strongly regular:

sage: g = graphs.CompleteGraph(5).complement()
sage: g.is_strongly_regular()

The empty graph is not strongly regular:

sage: g = graphs.EmptyGraph()
sage: g.is_strongly_regular()

Table Of Contents

Previous topic

Fast dense graphs

Next topic

Static Sparse Graphs

This Page