Arborescence (graph theory)

In graph theory, an arborescence is a directed graph where there exists a vertex r (called the root) such that, for any other vertex v, there is exactly one directed walk from r to v (noting that the root r is unique).[1] An arborescence is thus the directed-graph form of a rooted tree, understood here as an undirected graph.[2][3] An arborescence is also a directed rooted tree in which all edges point away from the root; a number of other equivalent characterizations exist.[4][5]

Every arborescence is a directed acyclic graph (DAG), but not every DAG is an arborescence.

  1. ^ Darij Grinberg (2 August 2023). "An introduction to graph theory (Text for Math 530 in Spring 2022 at Drexel University)" (PDF). Darij Grinberg, Ludwig-Maximilians-Universität München. p. 187. Retrieved 2 July 2024. Theorem 5.6.5, Statement A4: For each vertex v ∈ V, the multidigraph D has a unique walk from r to v.
  2. ^ Gordon, Gary (1989). "A greedoid polynomial which distinguishes rooted arborescences". Proceedings of the American Mathematical Society. 107 (2): 287–298. doi:10.1090/S0002-9939-1989-0967486-0.
  3. ^ Cite error: The named reference Williamson1985 was invoked but never defined (see the help page).
  4. ^ Jean-Claude Fournier (2013). Graphs Theory and Applications: With Exercises and Problems. John Wiley & Sons. pp. 94–95. ISBN 978-1-84821-070-7.
  5. ^ Jean Gallier (2011). Discrete Mathematics. Springer Science & Business Media. pp. 193–194. ISBN 978-1-4419-8046-5.