6-cycle double covers of cubic graphs

Details 6-cycle double covers of cubic graphs 6-cycle double covers of cubic graphs

2005-05-31

arxiv.org/abs/cs/0505088v4

Computer Science

Discrete Mathematics

This version fixes typos and minor technical problems, and updates references

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

6-cycle double covers of cubic graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with 6-cycle double covers of cubic graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and 6-cycle double covers of cubic graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-455534