1.4 Constructing Graphs from Other Graphs291.4 Constructing Graphs from Other GraphsWe have already seen a couple of ways in which we may associate with each graphanother graph: the complement (in the case of simple graphs) and the line graph.If we start with two graphs G and H rather than just one, a new graph may bedefined in several ways. For notational simplicity, we assume that G and H aresimple, so that each edge is an unordered pair of vertices; the concepts describedherecanbeextended without difficulty tothegeneral contextUNION AND INTERSECTIONTwo graphs are disjoint if theyhave no vertex in common, and edge-disjointifthey have no edge in common. The most basic ways of combining graphs are byThe union of simple graphs G and H is the graph GUHunionand intersectiolwith vertex set V(G)UV(H) and edge set E(G)UE(H). If G and H are disjoint.we refer to their union as a disjoint union, and generally denote it by G+HThese operations are associative and comnutative, and may be extended to anarbitrary number of graphs. It can be seen that a graph is disconnected if andonly if itisa disjointnion of two (nonnull) graphs. More generally, every graphG may be expressed uniquely (up to order) as a disjoint union of connected graphs(Exercise 1.4.1). These graphs are called the connected components, or simply thecomponents, of G.The number of components of G is denoted c(G). (The nullgraph has the anomalous property of being the only graph without components.)The intersection GnH of Gand H is defined analogously.(NotethatwherG and H are disjoint, their intersection is the null graph.) Figure 1.22 illustratesheseconcepts.ThegraphGUHshown inFigure1.22has just onecomponentwhereas the graph Gn H has two components.03GHGUHGnHFig. 1.22. The union and intersection of two graphsCARTESIANPRODUCTThere are also several ways offorming from two graphs a new graph whose verteset is the cartesian product of their vertex sets.These constructions are consequently referred to as 'products'. We now describe one of them
1.4 Constructing Graphs from Other Graphs 29 1.4 Constructing Graphs from Other Graphs We have already seen a couple of ways in which we may associate with each graph another graph: the complement (in the case of simple graphs) and the line graph. If we start with two graphs G and H rather than just one, a new graph may be defined in several ways. For notational simplicity, we assume that G and H are simple, so that each edge is an unordered pair of vertices; the concepts described here can be extended without difficulty to the general context. Union and Intersection Two graphs are disjoint if they have no vertex in common, and edge-disjoint if they have no edge in common. The most basic ways of combining graphs are by union and intersection. The union of simple graphs G and H is the graph G ∪ H with vertex set V (G) ∪ V (H) and edge set E(G) ∪ E(H). If G and H are disjoint, we refer to their union as a disjoint union, and generally denote it by G + H. These operations are associative and commutative, and may be extended to an arbitrary number of graphs. It can be seen that a graph is disconnected if and only if it is a disjoint union of two (nonnull) graphs. More generally, every graph G may be expressed uniquely (up to order) as a disjoint union of connected graphs (Exercise 1.4.1). These graphs are called the connected components, or simply the components, of G. The number of components of G is denoted c(G). (The null graph has the anomalous property of being the only graph without components.) The intersection G ∩ H of G and H is defined analogously. (Note that when G and H are disjoint, their intersection is the null graph.) Figure 1.22 illustrates these concepts. The graph G ∪ H shown in Figure 1.22 has just one component, whereas the graph G ∩ H has two components. 11 1 2 2 2 1 2 4 5 3 4 3 5 3 3 GH G ∪ H G ∩ H Fig. 1.22. The union and intersection of two graphs Cartesian Product There are also several ways of forming from two graphs a new graph whose vertex set is the cartesian product of their vertex sets. These constructions are consequently referred to as ‘products’. We now describe one of them
301 GraphsThe cartesian product of simple graphs G and H is the graph G H whosvertex set is V(G) × V(H) and whose edge set is the set of all pairs (ui, vi)(u2, 2)such that either uiu2 E E(G) and vi = v2, or Viwz e E(H) and u, = w. Thfor each edge uiu2 of G and each edge viu2 of H, there are four edges in G Hnamely (u1,vi)(u2,ui), (u1,v2)(u2, v2), (u1,v1)(u1, v2), and (u2,Ui)(u2, v2) (seeFigure 1.23a); the notation used for the cartesian product reflects this fact. Moregenerally, the cartesian product Pm Pn of two paths is the (m x n)-grid. Anexampleisshown in Figure1.23b(b)(a)Fig.1.23.(a)ThecartesianproductK,Ka+and (b)the(5x4)-gridFor n ≥ 3, the cartesian product Cn K2 is a polyhedral graph, the n-prism;the 3-prism.4-prism. and 5-prism are commonly called the triangular prism.thecube,andthepentagonal prism (seeFigure1.24).Thecartesianproductis arguablythe most basic of graph products. There exist a number of others, each arisingnaturally in various contexts. We encounter several of these in later chapters.人Fig. 1.24. The triangular and pentagonal prisms
30 1 Graphs The cartesian product of simple graphs G and H is the graph G H whose vertex set is V (G)×V (H) and whose edge set is the set of all pairs (u1,v1)(u2,v2) such that either u1u2 ∈ E(G) and v1 = v2, or v1v2 ∈ E(H) and u1 = u2. Thus, for each edge u1u2 of G and each edge v1v2 of H, there are four edges in G H, namely (u1,v1)(u2,v1), (u1,v2)(u2,v2), (u1,v1)(u1,v2), and (u2,v1)(u2,v2) (see Figure 1.23a); the notation used for the cartesian product reflects this fact. More generally, the cartesian product Pm Pn of two paths is the (m × n)-grid. An example is shown in Figure 1.23b. u1 u2 v1 v2 (u1, v1) (u1, v2) (u2, v1) (u2, v2) (a) (b) Fig. 1.23. (a) The cartesian product K2 K2, and (b) the (5 × 4)-grid For n ≥ 3, the cartesian product Cn K2 is a polyhedral graph, the n-prism; the 3-prism, 4-prism, and 5-prism are commonly called the triangular prism, the cube, and the pentagonal prism (see Figure 1.24). The cartesian product is arguably the most basic of graph products. There exist a number of others, each arising naturally in various contexts. We encounter several of these in later chapters. Fig. 1.24. The triangular and pentagonal prisms
1.5 Directed Graphs31Exercises1.4.1Show that every graph may beexpressed uniquely (up toorder)asa disjointunion of connected graphs.1.4.2 Show that the rank over GF(2) of the incidence matrix of a graph G is n -c1.4.3 Show that the cartesian product is both associative and commutative1.4.4 Find an embedding of the cartesian product Cm Cn on the torus1.4.5a) Show that the cartesian product of two vertex-transitive graphs is vertexransitiveb) Give an example to show that the cartesian product of two edge-transitivegraphs need not be edge-transitive1.4.6a) Let G be a self-complementary graph and let P be a path of length threelisiointfromG.Form anewgraph H from GUPby joining thefirst and thirdvertices of P to each vertex of G. Show that H is self-complementaryb) Deduce (by appealingtoExercise1.2.16) thatthereexistsaself-complementarygraph on n vertices if and only if n = 0,1 (mod 4)1.5 Directed GraphsAlthough ma problems lend themselves to graph-thecoticforlationcept of a graph is sometimes not quite adequate. When dealing with problemsof traffic flow, for example, it is necessary to know which roads in the networkare one-way, and in which direction traffic is permitted. Clearly, a graph of thenetwork is not of much use in such a situation. What we need is a graph in whicheach link has an assigned orientation, namely a directed graph.Formally, a directed graph D is an ordered pair (V(D), A(D) consisting of a setV := V(D) of vertices and a set A := A(D), disjoint from V(D), of arcs, togetherwith an incidence function p that asstes with each arc of D an ordered paircessarily distinct) vertices of D. Ifa is an arc and p(a)=(u, ), thenof (nots said to join u to v; we also say that u dominates w. Thertexuisthetail of a, and the vertex u its head they are the two ends of a. Occasionally, theorientation of an arc is irrelevant to the discussion. In such instances, we refer tothe arc as an edge of the directed graph. The number of arcs in D is denoted bya(D). The vertices which dominate a vertex are its in-neighbours, those whichare dominated by the vertex its outneighbours. These sets are denoted by N(v)and N(u), respectively
1.5 Directed Graphs 31 Exercises 1.4.1 Show that every graph may be expressed uniquely (up to order) as a disjoint union of connected graphs. 1.4.2 Show that the rank over GF(2) of the incidence matrix of a graph G is n−c. 1.4.3 Show that the cartesian product is both associative and commutative. 1.4.4 Find an embedding of the cartesian product Cm Cn on the torus. 1.4.5 a) Show that the cartesian product of two vertex-transitive graphs is vertextransitive. b) Give an example to show that the cartesian product of two edge-transitive graphs need not be edge-transitive. 1.4.6 a) Let G be a self-complementary graph and let P be a path of length three disjoint from G. Form a new graph H from G∪P by joining the first and third vertices of P to each vertex of G. Show that H is self-complementary. b) Deduce (by appealing to Exercise 1.2.16) that there exists a self-complementary graph on n vertices if and only if n ≡ 0, 1 (mod 4). 1.5 Directed Graphs Although many problems lend themselves to graph-theoretic formulation, the concept of a graph is sometimes not quite adequate. When dealing with problems of traffic flow, for example, it is necessary to know which roads in the network are one-way, and in which direction traffic is permitted. Clearly, a graph of the network is not of much use in such a situation. What we need is a graph in which each link has an assigned orientation, namely a directed graph. Formally, a directed graph D is an ordered pair (V (D),A(D)) consisting of a set V := V (D) of vertices and a set A := A(D), disjoint from V (D), of arcs, together with an incidence function ψD that associates with each arc of D an ordered pair of (not necessarily distinct) vertices of D. If a is an arc and ψD(a)=(u,v), then a is said to join u to v; we also say that u dominates v. The vertex u is the tail of a, and the vertex v its head; they are the two ends of a. Occasionally, the orientation of an arc is irrelevant to the discussion. In such instances, we refer to the arc as an edge of the directed graph. The number of arcs in D is denoted by a(D). The vertices which dominate a vertex v are its in-neighbours, those which are dominated by the vertex its outneighbours. These sets are denoted by N − D (v) and N + D (v), respectively
321 GraphsFor convenience, we abbreviate the term 'directed graph' to digraph. A strictdigraph is one with no loops or parallel arcs (arcs with the same head and thesametail),With any digraph D, we can associate a graph G on the same vertex setsimply by replacing each arc by an edge with the same ends. This graph is theunderlying graph of D, denoted G(D). Conversely, any graph G can be regarded asa digraph, by replacing each of its edges by two oppositely oriented arcs with thesame ends: this digraph is the associated digraph of G, denoted D(G).One mayalsoobtainadigraph fromagraph G by replacing each edgeby just one of the twopossible arcs with the samle ends.Such a digraph is called an orientation of G.Weoccasionally use the symbol G to specify an orientation of G (even though a graphgenerlly has many orientations). An orientation of a simple graph is referred toas an oriented graph. One particularly interesting instance is an orientationofacompletegraph.Such an oriented graph is called atournamentbecauseit can beviewed as representing the results of a round-robin tournament, one in which eachteam plays every other team (and there are no ties).Digraphs, like graphs, have a simple pictorial representation. A digraph is represented by a diagram of its underlying graph together with arrows on its edgeseach arrow pointing towards the head of the corresponding arc. The four unlabelledournamentsonfourverticesareshown inFigure1.25 (seeExercise1.5.3a)AAAFig.1.25. The folabellU0Every concept that is valid for graphs automatically applies to digraphs tooFor example, the degree of a vertex u in a digraph D is simply the degree of u inG(D),theunderlyinggraph of D.Likewise,a digraph is said to be connected ifits underlying graph is connected.2 But there are concepts in which orientationsplay an essential role.For instance, the indegree d(u)of a vertex im D is thenumber of arcs with head v, and the outdegree db(u) of u is the number of arwith tail u. The mininnum indegree and outdegree of D are denoted by &-(D)and &+(D), respectively; likewise, the maximum indegree and outdegree of D are1 In such cases, we employ the same notation as for graphs (with G replaced by D)Thus the delegree of v in D is denoted by dp(o). These instances of identical notationwhichdiffersubstantively frotheir analogues for graphs.Thus the term 'connected digraph'does not appear there.only 'connected graph
32 1 Graphs For convenience, we abbreviate the term ‘directed graph’ to digraph. A strict digraph is one with no loops or parallel arcs (arcs with the same head and the same tail). With any digraph D, we can associate a graph G on the same vertex set simply by replacing each arc by an edge with the same ends. This graph is the underlying graph of D, denoted G(D). Conversely, any graph G can be regarded as a digraph, by replacing each of its edges by two oppositely oriented arcs with the same ends; this digraph is the associated digraph of G, denoted D(G). One may also obtain a digraph from a graph G by replacing each edge by just one of the two possible arcs with the same ends. Such a digraph is called an orientation of G. We occasionally use the symbol −→G to specify an orientation of G (even though a graph generally has many orientations). An orientation of a simple graph is referred to as an oriented graph. One particularly interesting instance is an orientation of a complete graph. Such an oriented graph is called a tournament, because it can be viewed as representing the results of a round-robin tournament, one in which each team plays every other team (and there are no ties). Digraphs, like graphs, have a simple pictorial representation. A digraph is represented by a diagram of its underlying graph together with arrows on its edges, each arrow pointing towards the head of the corresponding arc. The four unlabelled tournaments on four vertices are shown in Figure 1.25 (see Exercise 1.5.3a). Fig. 1.25. The four unlabelled tournaments on four vertices Every concept that is valid for graphs automatically applies to digraphs too. For example, the degree of a vertex v in a digraph D is simply the degree of v in G(D), the underlying graph of D. 1 Likewise, a digraph is said to be connected if its underlying graph is connected.2 But there are concepts in which orientations play an essential role. For instance, the indegree d− D(v) of a vertex v in D is the number of arcs with head v, and the outdegree d+ D(v) of v is the number of arcs with tail v. The minimum indegree and outdegree of D are denoted by δ−(D) and δ+(D), respectively; likewise, the maximum indegree and outdegree of D are 1 In such cases, we employ the same notation as for graphs (with G replaced by D). Thus the degree of v in D is denoted by dD(v). These instances of identical notation are recorded only once in the glossaries, namely for graphs. 2 The index includes only those definitions for digraphs which differ substantively from their analogues for graphs. Thus the term ‘connected digraph’ does not appear there, only ‘connected graph’
1.5 Directed Graphs33denoted △-(D) and △+(D), respectively. A digraph is k-diregularif each indegreeand each outdegree is equal to k.A vertex of indegree zero is called a source, oneof outdegree zero a sink.A directed path or directed cycle is an orientation of apath or cycle in which each vertex dominates its successor in the sequence.Therea notion of connectedness in digraphs which takes directions into account,snsas we shall see in Chapter2Two special digraphs are shown in Figure 1.26.The first of these is a 2-diregulaldigraph, the second a 3-diregular digraph (see Bondy (1978)); we adopt here theention of representing two oppositely oriented arcs by anedge. These digraphsconvecan both be constructed from the Fano plane (Exercise 1.5.9). They also possessother unusual properties,tobe described in Chapter 2(6)(a)Fig. 1.26. (a) the KolTindell digraph, and (b) a direPted analogue graphFurther examples of interesting digraphs can be derived from other mathemat.icalstructures.suchasgroups.Forexample.therejsanaturaldirected analopuof a Cayley graph. If I is a group, and S a subset of I not including the iden-lement, the Cayley digraph of I with respect to S is the digraph, denotedCD(T, S), whose vei set is I and in which vertex r dominates vertex y if andonly iy-dircted circulantiaCayleydigraphCD(Zn),whereis the group of integers modulo n. The Koh-Tindell digraph of Figure 1.26a is adirected circulant based on Z-With each digraph D, one may associate another digraph, D, obtained byreversing each arc of D.The digraph D is called the converse of D. Because theeofthecoverseis iusttheoriginal digraph.the converse of a digraph canbe thought of as its 'directional dual'. This point of view gives rise to a simple yetuseful principle.PRINCIPLE OF DIRECTIONAL DUALITYompanying 'dual'statement, obtained byAny statement about a digraph has an acoapplying the statementtotheconverseof thedigraph and reinterpreting itintermsof the original digraph
1.5 Directed Graphs 33 denoted ∆−(D) and ∆+(D), respectively. A digraph is k-diregular if each indegree and each outdegree is equal to k. A vertex of indegree zero is called a source, one of outdegree zero a sink. A directed path or directed cycle is an orientation of a path or cycle in which each vertex dominates its successor in the sequence. There is also a notion of connectedness in digraphs which takes directions into account, as we shall see in Chapter 2. Two special digraphs are shown in Figure 1.26. The first of these is a 2-diregular digraph, the second a 3-diregular digraph (see Bondy (1978)); we adopt here the convention of representing two oppositely oriented arcs by an edge. These digraphs can both be constructed from the Fano plane (Exercise 1.5.9). They also possess other unusual properties, to be described in Chapter 2. (a) (b) Fig. 1.26. (a) the Koh–Tindell digraph, and (b) a directed analogue of the Petersen graph Further examples of interesting digraphs can be derived from other mathematical structures, such as groups. For example, there is a natural directed analogue of a Cayley graph. If Γ is a group, and S a subset of Γ not including the identity element, the Cayley digraph of Γ with respect to S is the digraph, denoted CD(Γ,S), whose vertex set is Γ and in which vertex x dominates vertex y if and only if xy−1 ∈ S. A directed circulant is a Cayley digraph CD(Zn,S), where Zn is the group of integers modulo n. The Koh–Tindell digraph of Figure 1.26a is a directed circulant based on Z7. With each digraph D, one may associate another digraph, ←−D, obtained by reversing each arc of D. The digraph ←−D is called the converse of D. Because the converse of the converse is just the original digraph, the converse of a digraph can be thought of as its ‘directional dual’. This point of view gives rise to a simple yet useful principle. Principle of Directional Duality Any statement about a digraph has an accompanying ‘dual’ statement, obtained by applying the statement to the converse of the digraph and reinterpreting it in terms of the original digraph