Minimal chordal sense of direction and circulant graphs
<|reference_start|>Minimal chordal sense of direction and circulant graphs: A sense of direction is an edge labeling on graphs that follows a globally consistent scheme and is known to considerably reduce the complexity of several distributed problems. In this paper, we study a particular instance of sense of direction, called a chordal sense of direction (CSD). In special, we identify the class of k-regular graphs that admit a CSD with exactly k labels (a minimal CSD). We prove that connected graphs in this class are Hamiltonian and that the class is equivalent to that of circulant graphs, presenting an efficient (polynomial-time) way of recognizing it when the graphs' degree k is fixed.<|reference_end|>
@article{leao2005minimal,
    title={Minimal chordal sense of direction and circulant graphs},
    author={R. S. C. Leao, V. C. Barbosa},
    journal={Lecture Notes in Computer Science 4162 (2006), 670-680},
    year={2005},
    doi={10.1007/11821069_58},
    archivePrefix={arXiv},
    eprint={cs/0503009},
    primaryClass={cs.DM}
}