Directed Graph

Tournaments and Orientability §

• A tournament is a digraph in which any two vertices are joined by exactly one arc.

• A tournament is irreducible if it is impossible to split the set of vertices of into the disjoint sets so that each arc joining a vertex from and a vertex of is directed from to .

• A tournament is transitive if and imply the existence of

• (Wilson e23.6) A tournament is irreducible if and only if it is strongly connected

  • Proof: By Redei’s Theorem if a tournament is strongly connected, it is Hamiltonian

    If is a Hamiltonian tournament, then there is a Hamiltonian Cycle, but this means that for vertices we may follow the arcs in the cycle to go from to and to . Since this is true for any pair of vertices, it is impossible to divide the tournament to two sets of vertices based on the definition of irreducibility.

    If is not Hamiltonian, then it is not strongly connected by Redei’s Theorem. Now, this means that there exists two vertices and such that either there is no -path or no -path.

    If both do not exist, then we are done. Simply, set as the vertices reachable from and as the vertices reachable from and they clearly cannot meet from our stipulations.

    If say one does exist (assume the path), we may still perform the same partition where contains the vertices reachable from except for . Then, aside from , another vertex must be in that s connected to but not to as otherwise, we would have a strongly connected tournament.

• The underlying graph of a digraph is an undirected graph whose edges are the arcs of interpreted as unordered pairs

• A digraph is strongly connected if for any two vertices, there is a path from to and from to Otherwise, a digraph is weakly connected if there is a path from to and from to when we view the underlying graph.

• A digraph is balanced if, for every vertex

• Let be an undirected graph. An orientation of is an assignment of a direction to each edge to to produce a digraph.

• An oriented graph can be seen as the result of applying an orientation. More formally, it is a graph where no two vertices are connected by symmetric arcs. That is, has an edge to implies does not have an edge to .

  • If is oriented, we denote it as . .
  • A strong orientation is an orientation that results in a strongly oriented graph.

• (Wilson 22.1) Let be a connected undirected graph. is strongly connected if and only if each edge is contained in at least one cycle.

Traversals §

• An edge in is said to be traversed positively in some directed path if the edge conforms with how the path is traversed. Otherwise, it is traversed negatively

• Let be the incidence matrix for a graph . A signed path vector is a vector corresponding to a path in such that

  • (Mesbahi 2.6) Given a path with distinct initial and terminal vertices described by a signed path vector in digraph , the vector is such that

• An Eulerian Trail is a trail in a digraph which contains all arcs of the digraph

• A connected digraph is Eulerian if there exists an Eulerian Trail.

• (Wilson 23.1) A connected graph is Eulerian if and only if for all

• Ghouila-Houri Criterion Let be a strongly connected digraph with vertices. If and for each vertex then is Hamiltonian

• (Wilson 23.3) Redei’s Theorem.

  • Every non-Hamiltonian tournament is semi-Hamiltonian.
  • Every strongly connected tournament is Hamiltonian.

Link §

• Wilson

• Mesbahi and Egerstedt

• Fundamental Constructs of Graph Theory

• Trails, Walks, Paths and Cycles