2005/05/31 by Rodrigo S. C. Leão, Leao, Rodrigo S. C., Valmir C. Barbosa +1
Computer Science · Engineering · #Advanced Graph Theory Research #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #G.2.2 #Graph Labeling and Dimension Problems #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.cs/0505088
openalex publication_date 2005/05/31 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.