Minimal chordal sense of direction and circulant graphs
| dc.creator | Leao, R. S. C. | |
| dc.creator | Barbosa, V. C. | |
| dc.date | 2005-03-03 | |
| dc.date.accessioned | 2026-07-07T07:46:33Z | |
| dc.date.available | 2026-07-07T07:46:33Z | |
| dc.description | 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. | |
| dc.identifier | https://arxiv.org/abs/cs/0503009 | |
| dc.identifier | http://arxiv.org/abs/cs/0503009 | |
| dc.identifier | Lecture Notes in Computer Science 4162 (2006), 670-680 | |
| dc.identifier | doi:10.1007/11821069_58 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/123866 | |
| dc.subject | Discrete Mathematics | |
| dc.subject | G.2.1; G.2.2 | |
| dc.title | Minimal chordal sense of direction and circulant graphs | |
| dc.type | text |