Asteroidal triples¶

This module contains the following function:

is_asteroidal_triple_free()

Test if the input graph is asteroidal triple-free

Definition¶

Three independent vertices of a graph form an asteroidal triple if every two of them are connected by a path avoiding the neighborhood of the third one. A graph is asteroidal triple-free (AT-free, for short) if it contains no asteroidal triple [LB1962].

Use graph_classes.AT_free.description() to get some known properties of AT-free graphs, or visit this page.

Algorithm¶

This module implements the Straightforward algorithm recalled in [Koh2004] and due to [LB1962] for testing if a graph is AT-free or not. This algorithm has time complexity in \(O(n^3)\) and space complexity in \(O(n^2)\).

This algorithm uses the connected structure of the graph, stored into a \(n\times n\) matrix \(M\). This matrix is such that \(M[u][v]==0\) if \(v\in (\{u\}\cup N(u))\), and otherwise \(M[u][v]\) is the unique identifier (a strictly positive integer) of the connected component of \(G\setminus(\{u\}\cup N(u))\) to which \(v\) belongs. This connected structure can be computed in time \(O(n(n+m))\) using \(n\) BFS.

Now, a triple \(u, v, w\in V\) is an asteroidal triple if and only if it satisfies \(M[u][v]==M[u][w]\) and \(M[v][u]==M[v][w]\) and \(M[w][u]==M[w][v]\), assuming all these values are positive. Indeed, if \(M[u][v]==M[u][w]\), \(v\) and \(w\) are in the same connected component of \(G\setminus(\{u\}\cup N(u))\), and so there is a path between \(v\) and \(w\) avoiding the neighborhood of \(u\). The algorithm iterates over all triples.

Functions¶

sage.graphs.asteroidal_triples.is_asteroidal_triple_free(G, certificate=False)[source]¶

Test if the input graph is asteroidal triple-free.

An independent set of three vertices such that each pair is joined by a path that avoids the neighborhood of the third one is called an asteroidal triple. A graph is asteroidal triple-free (AT-free) if it contains no asteroidal triples. See the module's documentation for more details.

This method returns True if the graph is AT-free and False otherwise.

INPUT:

G – a Graph
certificate – boolean (default: False); by default, this method returns True if the graph is asteroidal triple-free and False otherwise. When certificate==True, this method returns in addition a list of three vertices forming an asteroidal triple if such a triple is found, and the empty list otherwise.

EXAMPLES:

The complete graph is AT-free, as well as its line graph:

Sage

sage: G = graphs.CompleteGraph(5)
sage: G.is_asteroidal_triple_free()
True
sage: G.is_asteroidal_triple_free(certificate=True)
(True, [])
sage: LG = G.line_graph()
sage: LG.is_asteroidal_triple_free()
True
sage: LLG = LG.line_graph()
sage: LLG.is_asteroidal_triple_free()
False

Python

>>> from sage.all import *
>>> G = graphs.CompleteGraph(Integer(5))
>>> G.is_asteroidal_triple_free()
True
>>> G.is_asteroidal_triple_free(certificate=True)
(True, [])
>>> LG = G.line_graph()
>>> LG.is_asteroidal_triple_free()
True
>>> LLG = LG.line_graph()
>>> LLG.is_asteroidal_triple_free()
False

The PetersenGraph is not AT-free:

Sage

sage: from sage.graphs.asteroidal_triples import *
sage: G = graphs.PetersenGraph()
sage: G.is_asteroidal_triple_free()
False
sage: G.is_asteroidal_triple_free(certificate=True)
(False, [0, 2, 6])

Python

>>> from sage.all import *
>>> from sage.graphs.asteroidal_triples import *
>>> G = graphs.PetersenGraph()
>>> G.is_asteroidal_triple_free()
False
>>> G.is_asteroidal_triple_free(certificate=True)
(False, [0, 2, 6])