The geodesic structure of a graph 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 connected 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.

, , , , , , ,
doi.org/10.1016/j.disc.2012.09.022, hdl.handle.net/1765/72723
Discrete Mathematics
Erasmus School of Economics

Mulder, M., & Nebeský, L. (2013). Guides and shortcuts in graphs. Discrete Mathematics, 313(19), 1897–1907. doi:10.1016/j.disc.2012.09.022