The geodesic structure of a graphs appears to be a very rich structure. There are many ways to describe this structure, each of which captures only some aspects. Ternary algebras are for this purpose very useful and have a long tradition. We study two instances: signpost systems, and a special case of which, step systems. Signpost systems were already used to characterize graph classes. Here we use these for the study of the geodesic structure of a spanning subgraph F with respect to its host graph G. Such a signpost system is called a guide to (F,G). Our main results are: the characterization of the step system of a cycle, the characterization of guides for spanning trees and hamiltonian cycles.

geodesic structure, guide, hamiltonian cycle, shortcut, signpost system, spanning tree
Erasmus School of Economics
hdl.handle.net/1765/30589
Econometric Institute Research Papers
Report / Econometric Institute, Erasmus University Rotterdam
Erasmus School of Economics

Mulder, H.M, & Nebesky, L. (2011). Guides and Shortcuts in Graphs (No. EI 2011-38). Report / Econometric Institute, Erasmus University Rotterdam (pp. 1–23). Erasmus School of Economics. Retrieved from http://hdl.handle.net/1765/30589