According to Theorem 15.5 a nontrivial graph G has a strong orientation if and only if G

Let V = {P(n),Q(n),R(n)} be the set of the following open sentences involving integers n: P(n): n is even. Q(n): 4n + 1 is even. R(n): n2 is even. Draw a digraph D with vertex set V , where for A,B V , there is a directed edge from A to B if n Z,A B is a true statement.

Let S = {3, 6, 9, 18}. (a) The vertex set of a graph G is S and two vertices i and j are adjacent if either i | j or j | i. Draw the graph G. (b) The vertex set of a digraph D is S and (i, j) is an arc of D if i | j. Draw the digraph D. (c) What can you say about the graph G in (a) and the digraph D in (b)?

(a) The vertex set of a digraph D is V (D) = {M1,M2,M3,M4}, where M1,M2,M3 and M4 are the four 2 2 matrices M1 = _ 0 1 0 0 _, M2 = _ 0 0 1 0 _, M3 = _ 1 1 0 0 _ and M4 = _ 0 0 1 1 _. There is a directed edge from the vertex Mi to the vertex Mj (i 6= j) if MiMj = _ 0 0 0 0 _. Draw the digraph D. (b) Use the idea expressed in (a) to define and draw another digraph D.

A digraph D contains three vertices with indegree 0 and three vertices with indegree 2. The remaining two vertices of D have indegree 1. One of these eight vertices has outdegree 0 and another has outdegree 2. The remaining vertices have the same outdegree. What is this outdegree? Draw a digraph having these properties.

Let D be a digraph obtained by assigning a direction to each edge of the cycle Cn of order n 3. Prove that D either contains an even number of vertices having indegree 0 or an even number of vertices having outdegree 0.

Determine the adjacency matrix for each digraph in Figure 15.11.

(a) Prove that if a connected digraph D is strong, then od v > 0 and id v > 0 for every vertex v of D. (b) Is the converse of (a) true?

Use the technique employed in the proof of Theorem 15.5 to construct a strong orientation of the graph G of Figure 15.12.

Determine all (non-isomorphic) orientations of the 5-cycle C5.

Determine the number of orientations of the star K1,t (t 1).

Determine the number of orientations of the graph G in Figure 15.13.

Let G be a connected graph of order n 3. Prove that there is an orientation of G in which no directed path has length 2 if and only if G is bipartite.

The converse ~D of a digraph D is obtained from D by reversing the direction of every arc of D. Show that a digraph D is strong if and only if its converse ~D is strong.

(a) Does there exist a digraph D of order n 3 in which no two vertices of D have the same outdegree but every two vertices of D have the same indegree? (b) Does there exist a digraph D of order n 3 such that no two vertices of D have the same indegree and no two vertices of D have the same outdegree?

A digraph D is Eulerian if D contains a directed circuit that contains every directed edge of D. Let D be a connected digraph of order n 3 with V (D) = {v1, v2, , vn}. Prove the following. (a) The digraph D is Eulerian if and only if od vi = id vi for 1 i n. (b) If od vi id vi for 1 i n, then D is Eulerian. (c) If Pn i=1 | od vi id vi| = 0, then D is Eulerian.

Prove that a graph G has an Eulerian orientation (see Exercise 15) if and only if G is Eulerian.

According to Theorem 15.5 a nontrivial graph G has a strong orientation if and only if G is connected and contains no bridges. (a) Prove that if G is a nontrivial connected graph with at most two bridges, then there exists an orientation D of G having the property that if u and v are any two vertices of D, there is either a directed u v path or a directed v u path. (b) Show that the statement (a) is false if G contains three bridges.

Does there exist a strong orientation D of a graph G and two vertices u and v of G such that ~dD(u, v) 6= dG(u, v) and ~dD(v, u) 6= dG(v, u)?

Prove that if every vertex of a digraph D has positive outdegree, then D contains a directed cycle.

Let G be a nontrivial connected graph without bridges. (a) Show that for every edge e of G and for every orientation of e, there exists an orientation of the remaining edges of G such that the resulting digraph is strong. (b) Show that (a) need not be true if we begin with an orientation of two edges of G.

Let D be a digraph with V (D) = {1, 3, 5, 9, 11, 13} and let A = {2, 8} and B = {4, 10}. A vertex i is adjacent to a vertex j in D if j i A and j is adjacent to i if j i B. Is D strong?

(a) Two people A and B play a game on the complete graph K4. These two people alternate assigning a direction to an edge, beginning with A. It is the goal of A is to produce a strong orientation of K4 while it is the goal of B to stop A from doing this. If both players play perfectly, who will win the game? On which turn will the game end? (b) What variation of this game is suggested and what is the outcome of this game?

Let T be a nontrivial tree and let r and s be two distinct vertices of T . Let D be the digraph with V (D) = V (T ) such that (u, v) is a directed edge of D if the r v path in T contains u or the s v path in T contains u. (Thus D may contain both (u, v) and (v, u)). What is the strong subdigraph of D of largest order?