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 and space complexity in
.
This algorithm uses the connected structure of the graph, stored into a
matrix
. This matrix is such that
if
, and otherwise
is the unique identifier (a strictly
positive integer) of the connected component of
to
which
belongs. This connected structure can be computed in time
using
BFS.
Now, a triple is an asteroidal triple if and only if it satisfies
and
and
, assuming all
these values are positive. Indeed, if
,
and
are in the
same connected component of
, and so there is a path
between
and
avoiding the neighborhood of
. 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 andFalse
otherwise.INPUT:
G
– a Graphcertificate
– (default: False) By default, this method returnsTrue
if the graph is asteroidal triple-free 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 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])