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 [LB62].

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 [Koh04] and due to [LB62] 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.

References

[Koh04]E. Kohler. Recognizing graphs without asteroidal triples. Journal of Discrete Algorithms 2(4):439-452, Dec. 2004 http://dx.doi.org/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:45-64, 1962.

Functions

sage.graphs.asteroidal_triples.is_asteroidal_triple_free(G, certificate=False)

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 is the graph is AT-free and False otherwise.

INPUT:

  • G – a Graph
  • certificate – (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: from sage.graphs.asteroidal_triples import *
sage: G = graphs.CompleteGraph(5)
sage: is_asteroidal_triple_free(G)
True
sage: is_asteroidal_triple_free(G, certificate=True)
(True, [])
sage: LG = G.line_graph()
sage: is_asteroidal_triple_free(LG)
True
sage: LLG = LG.line_graph()
sage: is_asteroidal_triple_free(LLG)
False

The PetersenGraph is not AT-free:

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