Weakly chordal graphs¶
This module deals with everything related to weakly chordal graphs. It currently contains the following functions:
is_long_hole_free() |
Tests whether g contains an induced cycle of length at least 5. |
is_long_antihole_free() |
Tests whether g contains an induced anticycle of length at least 5. |
is_weakly_chordal() |
Tests whether g is weakly chordal. |
Author:
- Birk Eisermann (initial implementation)
- Nathann Cohen (some doc and optimization)
REFERENCES:
[NikolopoulosPalios07] | (1, 2) Nikolopoulos, S.D. and Palios, L. Detecting holes and antiholes in graphs Algorithmica, 2007 Vol. 47, number 2, pages 119–138 http://www.cs.uoi.gr/~stavros/C-Papers/C-2004-SODA.pdf |
Methods¶
-
sage.graphs.weakly_chordal.
is_long_antihole_free
(g, certificate=False)¶ Tests whether the given graph contains an induced subgraph that is isomorphic to the complement of a cycle of length at least 5.
INPUT:
certificate
– boolean (default:False
)Whether to return a certificate. When
certificate = True
, then the function returns(False, Antihole)
ifg
contains an induced complement of a cycle of length at least 5 returned asAntihole
.(True, [])
ifg
does not contain an induced complement of a cycle of length at least 5. For this case it is not known how to provide a certificate.
When
certificate = False
, the function returns justTrue
orFalse
accordingly.
ALGORITHM:
This algorithm tries to find a cycle in the graph of all induced \(\overline{P_4}\) of \(g\), where two copies \(\overline{P}\) and \(\overline{P'}\) of \(\overline{P_4}\) are adjacent if there exists a (not necessarily induced) copy of \(\overline{P_5}=u_1u_2u_3u_4u_5\) such that \(\overline{P}=u_1u_2u_3u_4\) and \(\overline{P'}=u_2u_3u_4u_5\).
This is done through a depth-first-search. For efficiency, the auxiliary graph is constructed on-the-fly and never stored in memory.
The run time of this algorithm is \(O(m^2)\) [NikolopoulosPalios07] ( where \(m\) is the number of edges of the graph ) .
EXAMPLES:
The Petersen Graph contains an antihole:
sage: g = graphs.PetersenGraph() sage: g.is_long_antihole_free() False
The complement of a cycle is an antihole:
sage: g = graphs.CycleGraph(6).complement() sage: r,a = g.is_long_antihole_free(certificate=True) sage: r False sage: a.complement().is_isomorphic( graphs.CycleGraph(6) ) True
TESTS:
Further tests:
sage: g = Graph({0:[6,7],1:[7,8],2:[8,9],3:[9,10],4:[10,11],5:[11,6],6:[0,5,7],7:[0,1,6],8:[1,2,9],9:[2,3,8],10:[3,4,11],11:[4,5,10]}).complement() sage: r,a = g.is_long_antihole_free(certificate=True) sage: r False sage: a.complement().is_isomorphic( graphs.CycleGraph(9) ) True
-
sage.graphs.weakly_chordal.
is_long_hole_free
(g, certificate=False)¶ Tests whether
g
contains an induced cycle of length at least 5.INPUT:
certificate
– boolean (default:False
)Whether to return a certificate. When
certificate = True
, then the function returns(True, [])
ifg
does not contain such a cycle. For this case, it is not known how to provide a certificate.(False, Hole)
ifg
contains an induced cycle of length at least 5.Hole
returns this cycle.
If
certificate = False
, the function returns justTrue
orFalse
accordingly.
ALGORITHM:
This algorithm tries to find a cycle in the graph of all induced \(P_4\) of \(g\), where two copies \(P\) and \(P'\) of \(P_4\) are adjacent if there exists a (not necessarily induced) copy of \(P_5=u_1u_2u_3u_4u_5\) such that \(P=u_1u_2u_3u_4\) and \(P'=u_2u_3u_4u_5\).
This is done through a depth-first-search. For efficiency, the auxiliary graph is constructed on-the-fly and never stored in memory.
The run time of this algorithm is \(O(m^2)\) [NikolopoulosPalios07] ( where \(m\) is the number of edges of the graph ) .
EXAMPLES:
The Petersen Graph contains a hole:
sage: g = graphs.PetersenGraph() sage: g.is_long_hole_free() False
The following graph contains a hole, which we want to display:
sage: g = graphs.FlowerSnark() sage: r,h = g.is_long_hole_free(certificate=True) sage: r False sage: Graph(h).is_isomorphic(graphs.CycleGraph(h.order())) True
TESTS:
Another graph with vertices 2, ..., 8, 10:
sage: g = Graph({2:[3,8],3:[2,4],4:[3,8,10],5:[6,10],6:[5,7],7:[6,8],8:[2,4,7,10],10:[4,5,8]}) sage: r,hole = g.is_long_hole_free(certificate=True) sage: r False sage: hole Subgraph of (): Graph on 5 vertices sage: hole.is_isomorphic(graphs.CycleGraph(hole.order())) True
-
sage.graphs.weakly_chordal.
is_weakly_chordal
(g, certificate=False)¶ Tests whether the given graph is weakly chordal, i.e., the graph and its complement have no induced cycle of length at least 5.
INPUT:
certificate
– Boolean value (default:False
) whether to return a certificate. Ifcertificate = False
, returnTrue
orFalse
according to the graph. Ifcertificate = True
, return(False, forbidden_subgraph)
when the graph contains a forbidden subgraph H, this graph is returned.(True, [])
when the graph is weakly chordal.- For this case, it is not known how to provide a certificate.
ALGORITHM:
This algorithm checks whether the graph
g
or its complement contain an induced cycle of length at least 5.Using is_long_hole_free() and is_long_antihole_free() yields a run time of \(O(m^2)\) (where \(m\) is the number of edges of the graph).
EXAMPLES:
The Petersen Graph is not weakly chordal and contains a hole:
sage: g = graphs.PetersenGraph() sage: r,s = g.is_weakly_chordal(certificate = True) sage: r False sage: l = len(s.vertices()) sage: s.is_isomorphic( graphs.CycleGraph(l) ) True