# 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

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.

## Index¶

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

## Functions¶

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.

INPUT:

• 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.

EXAMPLES:

Petersen’s graph is strongly regular:

sage: g = graphs.PetersenGraph()
sage: g.is_strongly_regular()
True
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()
True
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()
False


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

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


Completements of complete graphs are not strongly regular:

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


The empty graph is not strongly regular:

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