next | previous | forward | backward | up | index | toc

graphComplement -- computes the complement of a graph

Synopsis

• Usage:
L' = graphComplement L
T = graphComplement S
H = graphComplement G
• Inputs:
• L, a list, containing graphs in various formats
• S, , a graph encoded in either Sparse6 or Graph6 format
• G, ,
• Optional inputs:
• OnlyIfSmaller => , default value false, when true, then the smaller (fewer edges) of the graph and its complement are returned
• Outputs:
• L', a list, the graph complement of the elements of $L$ stored in Graph6 format
• T, , the graph complement of $S$ stored in the same format at $S$
• H, , the graph complement of $G$

Description

This method computes the graph complement of the input graph and returns the result in the same format.

 i1 : graphComplement "Dhc" o1 = DUW i2 : graphComplement graph {{1,2},{2,3},{3,4},{4,5},{1,5}} o2 = Graph{0 => {2, 3}} 1 => {3, 4} 2 => {0, 4} 3 => {0, 1} 4 => {2, 1} o2 : Graph

Batch calls can be performed considerably faster when using the List input format. However, care should be taken as the returned list is entirely in Graph6 or Sparse6 format.

 i3 : G = generateBipartiteGraphs 7; i4 : time graphComplement G; -- used 0.00048333s (cpu); 0.00040246s (thread); 0s (gc) i5 : time (graphComplement \ G); -- used 0.112055s (cpu); 0.109085s (thread); 0s (gc)

Ways to use graphComplement :

• graphComplement(Graph)
• graphComplement(List)
• graphComplement(String)

For the programmer

The object graphComplement is .