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 vertex￾transitive. 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 con￾cept 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