Guides and Shortcuts in Graphs
January 2011
Research Paper
pp 1-23.
This publication is part of collection
| Related Files |
|---|
View PDF Version
(EI2011-38.pdf, 0.3MB) |
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.
Keywords
Automatically Extracted Terms
- system
- axiom
- graph
- signpost system
- signpost
- step system
- guide
- signpost systems
- lemma
- cycle
- geodesic structure
- satis fies axioms
- geodesic
- structure
- ternary
- proof
- induction
- characterization
- x ∈ v
- graph g
