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 string, a graph encoded in either Sparse6 or Graph6 format
- G, a graph,
Optional inputs:
- OnlyIfSmaller => a Boolean value, 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, a string, the graph complement of $S$ stored in the same format at $S$
- H, a graph, the graph complement of $G$

Description

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

For graphs as defined in the EdgeIdeals package, one can use the complementGraph method to achieve the same effect; however, this method provides the option of not taking the complement if the complement has more edges than the graph itself.

i1 : R = QQ[a..e];

i2 : graphComplement cycle R

o2 = Graph{"edges" => {{a, c}, {a, d}, {b, d}, {b, e}, {c, e}}}
           "ring" => R
           "vertices" => {a, b, c, d, e}

o2 : Graph

i3 : graphComplement "Dhc"

o3 = DUW

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.

i4 : G = generateBipartiteGraphs 7;

i5 : time graphComplement G;
     -- used 0.000372513 seconds

i6 : time (graphComplement \ G);
     -- used 0.0680761 seconds

Ways to use graphComplement :

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

For the programmer

The object graphComplement is a method function with options.

graphComplement -- computes the complement of a graph

Synopsis

Description

See also

Ways to use graphComplement :

For the programmer