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 data_structures/binary_matrix.pxd, 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.

For an overview of graph data structures in sage, see overview.

Index

Cython functions

dense_graph_init

Fill a binary matrix with the information from a Sage (di)graph.

Python functions

is_strongly_regular()

Check whether the graph is strongly regular

is_triangle_free()

Check whether \(G\) is triangle free

triangles_count()

Return the number of triangles containing \(v\), for every \(v\)

connected_subgraph_iterator()

Iterator over the induced connected subgraphs of order at most \(k\)

Functions

sage.graphs.base.static_dense_graph.connected_subgraph_iterator(G, k=None, vertices_only=False)

Iterator over the induced connected subgraphs of order at most \(k\).

This method implements a iterator over the induced connected subgraphs of the input (di)graph. An induced subgraph of a graph is another graph, formed from a subset of the vertices of the graph and all of the edges connecting pairs of vertices in that subset (Wikipedia article Induced_subgraph).

As for method sage.graphs.generic_graph.connected_components(), edge orientation is ignored. Hence, the directed graph with a single arc \(0 \to 1\) is considered connected.

INPUT:

  • G – a Graph or a DiGraph; loops and multiple edges are allowed

  • k – (optional) integer; maximum order of the connected subgraphs to report; by default, the method iterates over all connected subgraphs (equivalent to k == n)

  • vertices_only – boolean (default: False); whether to return (Di)Graph or list of vertices

EXAMPLES:

sage: G = DiGraph([(1, 2), (2, 3), (3, 4), (4, 2)])
sage: list(G.connected_subgraph_iterator())
[Subgraph of (): Digraph on 1 vertex,
 Subgraph of (): Digraph on 2 vertices,
 Subgraph of (): Digraph on 3 vertices,
 Subgraph of (): Digraph on 4 vertices,
 Subgraph of (): Digraph on 3 vertices,
 Subgraph of (): Digraph on 1 vertex,
 Subgraph of (): Digraph on 2 vertices,
 Subgraph of (): Digraph on 3 vertices,
 Subgraph of (): Digraph on 2 vertices,
 Subgraph of (): Digraph on 1 vertex,
 Subgraph of (): Digraph on 2 vertices,
 Subgraph of (): Digraph on 1 vertex]
sage: list(G.connected_subgraph_iterator(vertices_only=True))
[[1], [1, 2], [1, 2, 3], [1, 2, 3, 4], [1, 2, 4],
 [2], [2, 3], [2, 3, 4], [2, 4], [3], [3, 4], [4]]
sage: list(G.connected_subgraph_iterator(k=2))
[Subgraph of (): Digraph on 1 vertex,
 Subgraph of (): Digraph on 2 vertices,
 Subgraph of (): Digraph on 1 vertex,
 Subgraph of (): Digraph on 2 vertices,
 Subgraph of (): Digraph on 2 vertices,
 Subgraph of (): Digraph on 1 vertex,
 Subgraph of (): Digraph on 2 vertices,
 Subgraph of (): Digraph on 1 vertex]
sage: list(G.connected_subgraph_iterator(k=2, vertices_only=True))
[[1], [1, 2], [2], [2, 3], [2, 4], [3], [3, 4], [4]]

sage: G = DiGraph([(1, 2), (2, 1)])
sage: list(G.connected_subgraph_iterator())
[Subgraph of (): Digraph on 1 vertex,
 Subgraph of (): Digraph on 2 vertices,
 Subgraph of (): Digraph on 1 vertex]
sage: list(G.connected_subgraph_iterator(vertices_only=True))
[[1], [1, 2], [2]]
sage.graphs.base.static_dense_graph.is_strongly_regular(g, parameters=False)

Check whether the graph is strongly regular.

A simple 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 the Wikipedia article Strongly regular graph.

INPUT:

  • parameters – boolean (default: False); 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

If the input graph has loops or multiedges an exception is raised:

sage: Graph([(1,1),(2,2)],loops=True).is_strongly_regular()
Traceback (most recent call last):
...
ValueError: This method is not known to work on graphs with
loops. Perhaps this method can be updated to handle them, but in the
meantime if you want to use it please disallow loops using
allow_loops().

sage: Graph([(1,2),(1,2)],multiedges=True).is_strongly_regular()
Traceback (most recent call last):
...
ValueError: This method is not known to work on graphs with
multiedges. Perhaps this method can be updated to handle them, but in
the meantime if you want to use it please disallow multiedges using
allow_multiple_edges().
sage.graphs.base.static_dense_graph.is_triangle_free(G, certificate=False)

Check whether \(G\) is triangle free.

INPUT:

  • G – a Sage graph

  • certificate – boolean (default: False); whether to return a triangle if one is found

EXAMPLES:

sage: from sage.graphs.base.static_dense_graph import is_triangle_free
sage: is_triangle_free(graphs.PetersenGraph())
True
sage: K4 = graphs.CompleteGraph(4)
sage: is_triangle_free(K4)
False
sage: b, certif = is_triangle_free(K4, certificate=True)
sage: K4.subgraph(certif).is_clique()
True
sage.graphs.base.static_dense_graph.triangles_count(G)

Return the number of triangles containing \(v\), for every \(v\).

INPUT:

  • G – a simple Sage graph

EXAMPLES:

sage: from sage.graphs.base.static_dense_graph import triangles_count
sage: triangles_count(graphs.PetersenGraph())
{0: 0, 1: 0, 2: 0, 3: 0, 4: 0, 5: 0, 6: 0, 7: 0, 8: 0, 9: 0}
sage: sum(triangles_count(graphs.CompleteGraph(15)).values()) == 3 * binomial(15, 3)
True