Operations

Graph Operations

Modifying Functions

In addition to add!, add_edges!, and delete! the following functions modify the graph on which they operate.

• contract!(G,v,w): contract the edge (v,w) (merging w into v).
• complement!(G): overwrite G with its complement.

The remainder of the functions on this page do not modify their arguments; they produce a new graph.

Unary Operations

• G' or complement(G): return the complement of G.
• line_graph(G): line graph of G.
• induce(G,A): return the induced subgraph of G on vertices in the set A.
• trim(A,d=0): iteratively remove vertices of degree at most d.
• relabel(G): new graph isomorphic to G with vertices named 1,2,...,n.
• relabel(G,d): new graph isomorphic to G with vertices relabeled by the dictionary d.
• subdivide(G): new graph formed by replacing every edge of G with a path of length two.

Binary Operations

• disjoint_union(G,H): disjoint union of graphs G and H. This can also be written as G+H. Note that 2*G (or 2G) is the same as G+G. More generally, k*G (where k is an integer) gives a graph that is isomorphic to G+G+G+...+G (with k terms).
• union(G,H): new graph whose vertex [resp. edge] set is the union of the vertex [resp. edge] sets of the two graphs.
• cartesian(G,H): Cartesian product.
• lex(G,H) or G[H]: lexicographic product.
• join(G,H): join of G and H. May also be invoked with G ∨ H.