Minimal chordal sense of direction and circulant graphs

Details Minimal chordal sense of direction and circulant graphs Minimal chordal sense of direction and circulant graphs

2005-03-03

arxiv.org/abs/cs/0503009v1

Lecture Notes in Computer Science 4162 (2006), 670-680

Computer Science

Discrete Mathematics

Scientific paper

10.1007/11821069_58

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.

Affiliated with

Also associated with

No associations

Rating

Minimal chordal sense of direction and circulant 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 Minimal chordal sense of direction and circulant graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Minimal chordal sense of direction and circulant graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-24057