6-cycle double covers of cubic graphs
| dc.creator | Leao, Rodrigo S. C. | |
| dc.creator | Barbosa, Valmir C. | |
| dc.date | 2005-05-31 | |
| dc.date | 2009-04-17 | |
| dc.date.accessioned | 2026-07-07T13:05:08Z | |
| dc.date.available | 2026-07-07T13:05:08Z | |
| dc.description | A cycle double cover (CDC) of an undirected graph is a collection of the graph's cycles such that every edge of the graph belongs to exactly two cycles. We describe a constructive method for generating all the cubic graphs that have a 6-CDC (a CDC in which every cycle has length 6). As an application of the method, we prove that all such graphs have a Hamiltonian cycle. 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 [9], a particular instance of sense of direction, called a chordal sense of direction (CSD), is studied and the class of k-regular graphs that admit a CSD with exactly k labels (a minimal CSD) is analyzed. We now show that nearly all the cubic graphs in this class have a 6-CDC, the only exception being K4. | |
| dc.description | This version fixes typos and minor technical problems, and updates references | |
| dc.identifier | https://arxiv.org/abs/cs/0505088 | |
| dc.identifier | http://arxiv.org/abs/cs/0505088 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/227395 | |
| dc.subject | Discrete Mathematics | |
| dc.subject | G.2.2 | |
| dc.title | 6-cycle double covers of cubic graphs | |
| dc.type | text |