FindAsteroidalTriple - Maple Help

GraphTheory

 FindAsteroidalTriple
 find asteroidal triple
 IsAsteroidalTripleFree
 check if graph is free of asteroidal triples

 Calling Sequence FindAsteroidalTriple(G) IsAsteroidalTripleFree(G,opts)

Parameters

 G - graph opts - (optional) one or more options as specified below

Options

 • certificate : keyword option of the form certificate=true or certificate=false.
 Specifies whether a list representing the asteroidal triple should be returned in the event the graph contains an asteroidal triple. The default is false.

Description

 • FindAsteroidalTriple(G) returns an asteroidal triple as a list of vertices of G if one exists, and NULL otherwise.
 • IsAsteroidalTripleFree(G) returns true if G does not contain an asteroidal triple, and false if it does.

Definition

 • An asteroidal triple for a graph G is a triple (u,v,w) of non-adjacent vertices of G such that for each pair from the triple, there exists a path between them that does not intersect the third vertex or any of its neighbors.

Examples

 > $\mathrm{with}\left(\mathrm{GraphTheory}\right):$
 > $\mathrm{with}\left(\mathrm{SpecialGraphs}\right):$
 > $C≔\mathrm{CycleGraph}\left(5\right)$
 ${C}{≔}{\mathrm{Graph 1: an undirected graph with 5 vertices and 5 edge\left(s\right)}}$ (1)
 > $\mathrm{FindAsteroidalTriple}\left(C\right)$

The Petersen graph is not Asteroidal (that is, it does not contain an asteroidal triple), but it does contain an asteroidal path.

 > $P≔\mathrm{PetersenGraph}\left(\right)$
 ${P}{≔}{\mathrm{Graph 2: an undirected graph with 10 vertices and 15 edge\left(s\right)}}$ (2)
 > $\mathrm{FindAsteroidalTriple}\left(P\right)$
 $\left[{2}{,}{4}{,}{6}\right]$ (3)

Compatibility

 • The GraphTheory[FindAsteroidalTriple] and GraphTheory[IsAsteroidalTripleFree] commands were introduced in Maple 2024.