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.

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.

See Wikipedia article Strongly regular graph

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

Table Of Contents

Previous topic

Fast dense graphs

Next topic

Static Sparse Graphs

This Page