Template-Type: ReDIF-Paper 1.0
Author-Name: Mulder, H.M.
Author-Name-Last: Mulder
Author-Name-First: Martyn
Author-Name: Nebesky, L.
Author-Name-Last: Nebesky
Title: Guides and Shortcuts in Graphs
Abstract: 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.
Creation-Date: 2011-01-01
File-URL: https://repub.eur.nl/pub/30589/EI2011-38.pdf
File-Format: application/pdf
Series: RePEc:ems:eureir
Number: EI 2011-38
Keywords: geodesic structure, guide, hamiltonian cycle, shortcut, signpost system, spanning tree
Handle: RePEc:ems:eureir:30589