Advanced Graph Theory and Combinatorics

5Building New Graphs from Old Ones

5.1. Some natural transformations

We have already seen (induced) subgraphs in definition 1.16. With this process, we build a new graph from another one by deleting some edges and vertices. In this chapter, we present various constructions of graphs. Some resulting graphs will have fewer vertices and edges but for products, we will build larger graphs. At first, since V (G) and E(G) are sets (or multisets), Boolean operations may be applied to these sets. As an example, assume that two graphs G₁ and G₂ are defined over the same set of vertices. We could consider the set of edges E(G₁) ∪ E(G₂), E(G₁) ∩ E(G₂), etc. We can also consider the disjoint union of graphs where it is assumed that V (G₁) and V (G₂) are disjoint and the set of edges is the union E(G₁) ∪ E(G₂).

Let us start with the special case of a subgraph induced by the vertices at distance at most k from a given vertex. In Figure 5.1, we have represented the so-called Watkins snark¹ and the subgraph made up of the vertices at a distance at most four from the leftmost vertex in the representation.

For the next construction, it is useful to recall the reflexive and transitive closure discussed in section 1.2.1.

Figure 5.1. A subgraph of the Watkins snark

DEFINITION 5.1.– Let G = (V, E) be a digraph. The transitive closure is the smallest digraph G′ = (V, E′) having G as a subgraph such ...