Asteroidal triples¶
This module contains the following function:
is_asteroidal_triple_free() 
Test if the input graph is asteroidal triplefree 
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 triplefree (ATfree, for short) if it contains no asteroidal triple [LB62].
Use graph_classes.AT_free.description()
to get some known properties of
ATfree graphs, or visit this page.
Algorithm¶
This module implements the Straightforward algorithm recalled in [Koh04] and due to [LB62] for testing if a graph is ATfree 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.
References¶
[Koh04]  E. Kohler. Recognizing graphs without asteroidal triples. Journal of Discrete Algorithms 2(4):439452, Dec. 2004 doi:10.1016/j.jda.2004.04.005 
[LB62]  (1, 2) C. G. Lekkerkerker, J. Ch. Boland. Representation of a finite graph by a set of intervals on the real line. Fundamenta Mathematicae, 51:4564, 1962. 
Functions¶

sage.graphs.asteroidal_triples.
is_asteroidal_triple_free
(G, certificate=False)¶ Test if the input graph is asteroidal triplefree
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 triplefree (ATfree) if it contains no asteroidal triples. See the
module's documentation
for more details.This method returns
True
is the graph is ATfree andFalse
otherwise.INPUT:
G
– a Graphcertificate
– boolean (default:False
); by default, this method returnsTrue
if the graph is asteroidal triplefree andFalse
otherwise. Whencertificate==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 ATfree, as well as its line graph:
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
The PetersenGraph is not ATfree:
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])