Each of the functions given here apply to both graphs and digraphs. Further, each of the functions returns three values:
Given a graph G and a list v_1, ..., v_r, where v_i (i=1, ..., r) is either a vertex or a set of vertices, all of which belong to the graph G, form the subgraph of G induced on the subset of V(G) defined by v_1, ..., v_r.
Given a list e_1, ..., e_r, where e_i (i=1, ..., r) is either an edge or a set of edges, all of which belong to the graph G, form the subgraph of G whose vertex-set is V(G) and whose edge-set consists of the subset of E(G) defined by e_1, ..., e_r.
Given a graph G and a vertex v of G, form the graph with vertex set V(G) - { v }, and edge set E(G) - { edges of G incident with v }.
Given a graph G and a set U of vertices of G, form the graph with vertex set V(G) - U, and edge set E(G) - { edges of G incident with vertices of U }.
Given a graph G and an edge e of G, form the graph having vertex set V(G) and edge set E(G) - { e }.
Given a graph G and a subset F of the set of edges of G, form the graph having vertex set V(G) and edge set E(G) - F.
Given a (p, q) graph G with non-adjacent vertices u and v, form a (p, q + 1) graph H which contains the edges of G together with the additional edge {u, v}.
Given a (p, q) digraph G with non-adjacent vertices u and v, form a (p, q + 1) graph H which contains the edges of G together with the additional directed edge [u, v].
Given a (p, q) graph G and a set S = { {u_1, v_1}, ..., {u_r, v_r} } of pairs of non-adjacent vertices of G, construct a (p, q + r) graph H which contains the edges of G together with the r additional edges {u_i, v_i}.
Given a (p, q) digraph G and a set S = { [u_1, v_1], ..., [u_r, v_r] } of pairs of non-adjacent vertices of G, construct a (p, q + r) digraph H which contains the edges of G together with the r additional directed edges [u_i, v_i].
Given a graph G and a set-system P of the vertex-set V(G) of G, construct the quotient graph Q of G defined by P. Suppose the cells of the partition P are P_1, ..., P_r. The vertices of Q correspond to the cells P_i. Vertices v_i and v_j of Q are adjacent if and only if there is an edge in G joining a vertex in P_i with a vertex in P_j.
Unless otherwise stated, each of the functions described here apply to both graphs and digraphs. Further, each of the functions returns three values:
The complement of the graph G.
Given an edge e = {u, v} of the graph G, form the graph obtained by identifying the vertices u and v, and removing any multiple edges or loops from the resulting graph.
Given vertices u and v belonging to the graph G, return the graph obtained by identifying the vertices u and v, and removing any multiple edges or loops from the resulting graph.
Given a set S of vertices belonging to the graph G, return the graph obtained by identifying all of the vertices in S, and removing any multiple edges or loops from the resulting graph.
Given an edge e in the graph G, insert a new vertex of degree 2 in e.
Given an a set T of edges belonging to the graph G, insert a vertex of degree 2 in each edge belonging to the set T.
The line graph of the non-empty graph G. This function is not defined for digraphs.
Given a vertex u in a graph G, construct a graph H from G, where H has the same vertex set as G and the same edge set, except that the vertices that were the neighbours of u in G become the non-neighbours of u in H, and the vertices that were non-neighbours of u in G become the neighbours of u in H.
Given a set S of vertices belonging to the graph G, apply the function Switch(u), to each vertex of S in turn.
> G := CompleteGraph(5);
> E := EdgeSet(G);
> H := InsertVertex({ E | { 1, 3 }, { 1, 4 }, { 2, 4 }, { 2, 5 }, { 3, 5 } } );
> L := Union(H, CompleteGraph(1));
> L := L + { { L.11, L.6 }, { L.11, L.7 }, { L.11, L.8 }, { L.11, L.9 },
> { L.11, L.10 } };
> print L;
Graph
Vertex Neighbours
1 2 5 6 7 ;
2 1 3 8 10 ;
3 2 4 6 9 ;
4 3 5 7 8 ;
5 1 4 9 10 ;
6 1 3 11 ;
7 1 4 11 ;
8 2 4 11 ;
9 3 5 11 ;
10 2 5 11 ;
11 6 7 8 9 10 ;