O'Reilly logo

Advanced Graph Theory and Combinatorics by Michel Rigo

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

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 G1 and G2 are defined over the same set of vertices. We could consider the set of edges E(G1) ∪ E(G2), E(G1) ∩ E(G2), etc. We can also consider the disjoint union of graphs where it is assumed that V (G1) and V (G2) are disjoint and the set of edges is the union E(G1) ∪ E(G2).

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 snark1 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.

image

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 ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required