Recursive Graphs, Recursive Labelings and Shortest Paths
Andrzej Proskurowski · SIAM Journal on Computing · 1981
We consider classes of undirected, not weighted graphs which have recursive representations; these include trees, maximal outplanar graphs, k-trees, chordal graphs, and minimally two-connected graphs. We investigate invariants of recursive labelings of some of these graphs. One consequence of the existence of such invariant relation is that we can describe a single-source, shortest-paths spanning tree in terms of the recursive representation. We also discuss reasons why we cannot do this as well for other types of recursive graphs.