Each of the functions described in this section applies both to 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 partition P of the vertex-set V(G) of G, construct the quotient graph Q of G defined by P. The partition is given as a set of subsets of V(G). 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.
> K6, V, E := CompleteGraph(6); > K6; Graph Vertex Neighbours
1 2 3 4 5 6 ; 2 1 3 4 5 6 ; 3 1 2 4 5 6 ; 4 1 2 3 5 6 ; 5 1 2 3 4 6 ; 6 1 2 3 4 5 ; > F1 := { E | {1,2}, {3, 4}, {5, 6} }; > G1, V1, E1 := K6 - F1; > G1; Graph Vertex Neighbours
1 3 4 5 6 ; 2 3 4 5 6 ; 3 1 2 5 6 ; 4 1 2 5 6 ; 5 1 2 3 4 ; 6 1 2 3 4 ;
> K9, V, E := CompleteGraph(9);
> P := { { V | 1, 2, 3}, { V | 4, 5, 6}, { V | 7, 8, 9} };
> Q := quo< K9 | P >;
> Q;
Graph
Vertex Neighbours
1 2 3 ;
2 1 3 ;
3 1 2 ;
Adds a new vertex to the graph G. The existing vertex and edge labels will be retained, but the support will become the standard support.
Adds a new vertex with label l to the graph G. The existing vertex and edge labels will be retained, but the support will become the standard support.
Adds n new vertices to the graph G. The existing vertex and edge labels will be retained, but the support will become the standard support.
Adds n new vertices to the graph G with labels from the sequence L. The existing vertex and edge labels will be retained, but the support will become the standard support.
Removes the ith vertex from the graph G. The support and existing edge or vertex labels will be retained.
Removes the vertices whose indices are in the sequence S from the graph G. The support and existing edge or vertex labels will be retained.
Adds a new edge between the ith and jth vertices of the graph G. If the set or sequence form is used, G must be undirected or directed respectively. The support and existing edge or vertex labels will be retained.
Adds a new edge with label l between the ith and jth vertices of the graph G. The support and existing edge or vertex labels will be retained.
Adds the edges specified in the sequence S to the graph G. The elements of S must be sets or sequences of two integers, depending on whether G is undirected or directed respectively. Each element of S will correspond to the edge between the ith and jth vertices of G, where i and j are the two integers in the element. The support and existing edge or vertex labels will be retained.
Adds the edges specified in the sequence S to the graph G, and assigns the corresponding label from the sequence L to each new edge. The elements of S must be sets or sequences of two integers, depending on whether G is undirected or directed respectively. Each element of S will correspond to the edge between the ith and jth vertices of G, where i and j are the two integers in the element. The support and existing edge or vertex labels will be retained.
Removes the edge between the ith and jth vertices of the graph G. If the set or sequence form is used, G must be undirected or directed respectively. The support and existing edge or vertex labels will be retained.
Removes the edges specified in the sequence S from the graph G. The elements of S must be sets or sequences of two integers, depending on whether G is undirected or directed respectively. Each element of S will correspond to the edge between the ith and jth vertices of G, where i and j are the two integers in the element. The support and existing edge or vertex labels will be retained.
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 (and loops if the graph is undirected) 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 (and loops if the graph is undirected) 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 (and loops if the graph is undirected) 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 an undirected graph G, construct an undirected 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 undirected 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));
> V := VertexSet(L);
> L := L + { { V.11, V.6 }, { V.11, V.7 }, { V.11, V.8 }, { V.11, V.9 },
> { V.11, V.10 } };
> 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 ;