6-cycle double covers of cubic graphs

@misc{citeulike:1586017, abstract = {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 [1], 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.}, author = {Leao, R. S. C. and Barbosa, V. C. }, citeulike-article-id = {1586017}, eprint = {cs/0505088}, keywords = {algorithms, graph}, month = {Jun}, posted-at = {2007-08-23 14:45:51}, priority = {2}, title = {6-cycle double covers of cubic graphs}, url = {http://arxiv.org/abs/cs/0505088}, year = {2005} }

TY - ELEC ID - citeulike:1586017 L3 - citeulike-article-id:1586017 TI - 6-cycle double covers of cubic graphs N2 - 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 [1], 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. KW - algorithms KW - graph AU - Leao, RSC AU - Barbosa, VC PY - 2005/Jun/03/ UR - http://arxiv.org/abs/cs/0505088 ER -