Cographs

A cograph is a \(P_4\)-free graph, that is a graph without induced path of order 4. Any cograph may be constructed, starting from the single vertex graph, by a sequence of join and disjoint union operations. See the Wikipedia article Cograph for more details on this graph class, and OEIS sequence A000084 to know the number of cographs of order \(n \geq 1\).

This module implements the following methods concerning cographs:

cographs()

Return an iterator over the cographs of order \(n\).

Methods

class sage.graphs.cographs.CoTree(name='root')[source]

Bases: object

Generic cotree node.

This data structure is used for the generation of cographs in cographs().

add_child(node)[source]

Add cotree node in the list of children of self.

INPUT:

  • node – a CoTree

EXAMPLES:

sage: from sage.graphs.cographs import CoTree
sage: T = CoTree('J')
sage: T.add_child(CoTree(1))
sage: T
[ J ( 1 ) ]

>>> from sage.all import *
>>> from sage.graphs.cographs import CoTree
>>> T = CoTree('J')
>>> T.add_child(CoTree(Integer(1)))
>>> T
[ J ( 1 ) ]
copy_tree(T)[source]

Make \(T\) a copy of self.

INPUT:

  • T – a CoTree

EXAMPLES:

sage: from sage.graphs.cographs import CoTree
sage: T = CoTree('J')
sage: T.add_child(CoTree(1))
sage: T.add_child(CoTree(2))
sage: T
[ J ( 1 ) ( 2 ) ]
sage: B =  CoTree('U')
sage: T.copy_tree(B)
sage: B
[ U ( 1 ) ( 2 ) ]

>>> from sage.all import *
>>> from sage.graphs.cographs import CoTree
>>> T = CoTree('J')
>>> T.add_child(CoTree(Integer(1)))
>>> T.add_child(CoTree(Integer(2)))
>>> T
[ J ( 1 ) ( 2 ) ]
>>> B =  CoTree('U')
>>> T.copy_tree(B)
>>> B
[ U ( 1 ) ( 2 ) ]
reset_info()[source]

Reset parameter info from all nodes of self.

EXAMPLES:

sage: from sage.graphs.cographs import CoTree
sage: T = CoTree(1)
sage: B = CoTree(2)
sage: T.add_child(B)
sage: C = CoTree(3)
sage: B.add_child(C)
sage: C.info = 'info'
sage: T.reset_info()
sage: C.info is None
True

>>> from sage.all import *
>>> from sage.graphs.cographs import CoTree
>>> T = CoTree(Integer(1))
>>> B = CoTree(Integer(2))
>>> T.add_child(B)
>>> C = CoTree(Integer(3))
>>> B.add_child(C)
>>> C.info = 'info'
>>> T.reset_info()
>>> C.info is None
True
sage.graphs.cographs.change_label(tree, status, counter)[source]

Set the names of the nodes of tree.

This is a helper method to method cographs().

The input tree is such that each node has as label its number of children. This method changes the label of each node so that a parallel node is labeled ‘U’, a series node is labeled ‘J’ and a leaf node gets a unique number.

INPUT:

  • tree – the tree to relabel

  • status – boolean; used to detect series (True) and parallel (False) internal nodes

  • counter – list; the first integer of the list is used to assign a unique number to the leaves of the tree

EXAMPLES:

sage: next(graphs.cographs(4, as_graph=True)).vertices()  # indirect doctest
[0, 1, 2, 3]

>>> from sage.all import *
>>> next(graphs.cographs(Integer(4), as_graph=True)).vertices()  # indirect doctest
[0, 1, 2, 3]
sage.graphs.cographs.cographs(n, as_graph=True, immutable=False)[source]

Return an iterator over the cographs of order \(n\).

A cograph is a \(P_4\)-free graph, that is a graph without induced path of order 4. Any cograph may be constructed, starting from the single vertex graph, by a sequence of sage.graphs.graph.Graph.join() and sage.graphs.generic_graph.GenericGraph.disjoint_union() operations. See the Wikipedia article Cograph for more details.

This method implements the generator of all cographs of order \(n\) proposed in [JPD2018]. The algorithm generates one by one every cotree with \(n\) nodes, and each cotree is generated by using its previous cotree. The time to construct the first cotree is \(O(n)\) and the time spent between two consecutive outputs is \(O(n)\). Hence, the overall complexity of the algorithm is \(O(n*M_n)\), where \(n\) is the number of nodes and \(M_n\) is the total number of cographs with \(n\) nodes (see OEIS sequence A000084).

INPUT:

  • n – integer larger or equal to 1

  • as_graph – boolean (default: True); whether to return graphs or the tree data structure encoding the graph

  • immutable – boolean (default: False); whether to return an immutable or a mutable graph. This parameter is used only when as_graph is True.

EXAMPLES:

The output can be either cotrees or graphs:

sage: for t in graphs.cographs(3, as_graph=False):
....:     print(t)
[ J ( 0 ) ( 1 ) ( 2 ) ]
[ J [ U ( 0 ) ( 1 ) ( 2 ) ] ]
[ J ( 0 ) [ U ( 1 ) ( 2 ) ] ]
[ J [ U ( 0 ) [ J ( 1 ) ( 2 ) ] ] ]
sage: for g in graphs.cographs(3, as_graph=True):
....:     print(g.edges(labels=False, sort=True))
[(0, 1), (0, 2), (1, 2)]
[]
[(0, 1), (0, 2)]
[(1, 2)]

>>> from sage.all import *
>>> for t in graphs.cographs(Integer(3), as_graph=False):
...     print(t)
[ J ( 0 ) ( 1 ) ( 2 ) ]
[ J [ U ( 0 ) ( 1 ) ( 2 ) ] ]
[ J ( 0 ) [ U ( 1 ) ( 2 ) ] ]
[ J [ U ( 0 ) [ J ( 1 ) ( 2 ) ] ] ]
>>> for g in graphs.cographs(Integer(3), as_graph=True):
...     print(g.edges(labels=False, sort=True))
[(0, 1), (0, 2), (1, 2)]
[]
[(0, 1), (0, 2)]
[(1, 2)]

Check that we agree with OEIS sequence A000084:

sage: [sum(1 for _ in graphs.cographs(n, as_graph=False))
....:  for n in range(1, 8)]
[1, 2, 4, 10, 24, 66, 180]

>>> from sage.all import *
>>> [sum(Integer(1) for _ in graphs.cographs(n, as_graph=False))
...  for n in range(Integer(1), Integer(8))]
[1, 2, 4, 10, 24, 66, 180]
sage.graphs.cographs.find_pivot(T)[source]

Search for a pivot node in \(T\).

This is a helper method to method cographs().

A node in \(T\) is a pivot if it is not a leaf, it does not induce a maximum partition and it is the first such node in the inverse postorder traversal.

INPUT:

  • T – a CoTree

EXAMPLES:

sage: next(graphs.cographs(3, as_graph=True)).vertices()  # indirect doctest
[0, 1, 2]

>>> from sage.all import *
>>> next(graphs.cographs(Integer(3), as_graph=True)).vertices()  # indirect doctest
[0, 1, 2]
sage.graphs.cographs.next_tree(T)[source]

Check if there is another tree after \(T\).

This is a helper method to method cographs().

This methods returns True if there is a tree after \(T\), and if so it modifies the input tree \(T\) that becomes the next tree.

INPUT:

  • T – a CoTree

EXAMPLES:

sage: next(graphs.cographs(3, as_graph=True)).vertices()  # indirect doctest
[0, 1, 2]

>>> from sage.all import *
>>> next(graphs.cographs(Integer(3), as_graph=True)).vertices()  # indirect doctest
[0, 1, 2]
sage.graphs.cographs.rebuild_node(u, P)[source]

Replace the subtree rooted at \(u\) by a subtree induced by partition \(P\).

This is a helper method to method cographs().

INPUT:

  • u – a CoTree

  • P – a partition encoding the new structure of the children of \(u\)

EXAMPLES:

sage: next(graphs.cographs(3, as_graph=True)).vertices()  # indirect doctest
[0, 1, 2]

>>> from sage.all import *
>>> next(graphs.cographs(Integer(3), as_graph=True)).vertices()  # indirect doctest
[0, 1, 2]
sage.graphs.cographs.tree_to_graph(tree, immutable=False)[source]

Return the cograph represented by tree.

This is a helper method to method cographs().

EXAMPLES:

sage: for t in graphs.cographs(3, as_graph=True):  # indirect doctest
....:     print(t.edges(labels=False, sort=True))
[(0, 1), (0, 2), (1, 2)]
[]
[(0, 1), (0, 2)]
[(1, 2)]

>>> from sage.all import *
>>> for t in graphs.cographs(Integer(3), as_graph=True):  # indirect doctest
...     print(t.edges(labels=False, sort=True))
[(0, 1), (0, 2), (1, 2)]
[]
[(0, 1), (0, 2)]
[(1, 2)]