Editing Rooted graph (section)

==Related concepts==
A special case of interest are [[rooted tree]]s, the [[Tree (graph theory)|trees]] with a distinguished root vertex. If the directed paths from the root in the rooted digraph are additionally restricted to be unique, then the notion obtained is that of (rooted) [[Arborescence (graph theory)|arborescence]]—the directed-graph equivalent of a rooted tree.<ref name="poly"/> A rooted graph contains an arborescence with the same root if and only if the whole graph can be reached from the root, and computer scientists have studied algorithmic problems of finding optimal arborescences.<ref>{{citation
 | last1 = Drescher | first1 = Matthew
 | last2 = Vetta | first2 = Adrian
 | doi = 10.1145/1798596.1798599
 | issue = 3
 | journal = ACM Trans. Algorithms
 | pages = 46:1–46:18
 | title = An Approximation Algorithm for the Maximum Leaf Spanning Arborescence Problem
 | volume = 6
 | year = 2010| s2cid = 13987985
 | url = https://escholarship.mcgill.ca/concern/theses/3n204190p
 }}.</ref>

Rooted graphs may be combined using the [[rooted product of graphs]].<ref>{{citation
 | last1 = Godsil | first1 = C. D. | author1-link = Chris Godsil | author2-link = Brendan McKay (mathematician) | last2 = McKay | first2 = B. D.
 | title = A new graph product and its spectrum
 | journal = Bull. Austral. Math. Soc.
 | volume = 18
 | year = 1978
 | issue = 1
 | pages = 21–28
 | mr = 0494910
 | url = http://cs.anu.edu.au/~bdm/papers/RootedProduct.pdf
 | doi = 10.1017/S0004972700007760| doi-access = free
 }}</ref>