# Term for the tree of all paths starting from a given vertex in a graph

What is the term for the tree (or a part of the tree) of all possible paths in a graph that start from a given (source) vertex?

This is the tree that is implicitly or explicitly constructed when doing shortest path search. It appears, for example, in a lecture on search of an MIT Artificial Intelligence course, but I didn't understand if it has a name.

This is not a search tree and not really a decision tree.

Mathematically, it is a covering tree, but is there a more appropriate term in the context of shortest path search?

It's the self-avoiding walk tree (SAW tree).

The trees seem to have been first considered by C.D. Godsil (Matchings and Walks in Graphs, Journal of Graph Theory 5(3):285–297, 1981; DOI link; just before Lemma 2.4), though Godsil doesn't use the name.

(And, yes, "self-avoiding walk" is just a mighty-long way of saying "path".)

• This does not look like a special term with a specific meaning. Of course a tree is a tree, and if it consists of self-avoiding walks, it is a tree of self-avoiding walks, or self-avoiding walk tree. I've found out that The Handbook of Artificial Intelligence by Avron Barr and Edward Feigenbaum also uses search tree term, so i will probably stick with search tree. Mar 19 '19 at 14:14
• Huh? You asked for a term for the trees you describe in the question. I gave you a specific term with that specific meaning. Perhaps it's not the term that is used in the community you're working with, but it is a specific answer to your question, and not some generic term that applies to anything at all. Mar 19 '19 at 14:20
• Sorry, i meant rather special term for the specific meaning, but self-avoiding walk tree seems to be just a combination of self-avoiding walk and tree. For example, google only finds 368 pages with "self-avoiding walk tree" in them (quoted)... Mar 19 '19 at 14:27
• Probably I should have added that i was interested in this object in the context of path search in a graph. Mar 19 '19 at 14:30
• By the way, Wikipedia currently defines self-avoiding walk chiefly for latices, and the term is not found in their Glossary of graph theory terms... Mar 20 '19 at 15:42

I've discovered that Nils Nilsson in Principles of Artificial Intelligence (1982) calls it just a search tree, and search tree is also used in The Handbook of Artificial Intelligence (1981) by Avron Barr and Edward Feigenbaum. I've also found a sufficiently recent paper Predicting the size of IDA*ʼs search tree (2013).

I will stick with search tree.