Minimal Chordal Sense of Direction and Circulant Graphs

DOI10.1007/11821069_58MaRDI QIDQ5756720zbMATH OpenOpenAlexFDO

Authors Rodrigo S. C. Leão, Valmir C. Barbosa

Publication date 5 September 2007

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/cs/0503009

zbMATH Keywords

Cayley graphsChordal sense of directionCirculant graphs

Mathematics Subject Classification ID

Eulerian and Hamiltonian graphs (05C45) Graph labelling (graceful graphs, bandwidth, etc.) (05C78) Distributed systems (68M14) Graph theory (including graph drawing) in computer science (68R10)

Abstract: 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.

Recommendations

• Minimal sense of direction in regular networks
• Minimal sense of direction and decision problems for Cayley graphs
• scientific article; zbMATH DE number 1151833
• scientific article; zbMATH DE number 1185591
• TOPOLOGICAL CONSTRAINTS FOR SENSE OF DIRECTION

Cited in

(4)

• scientific article; zbMATH DE number 1696678 (Why is no real title available?)
• Minimal sense of direction in regular networks
• Lower bounds for sense of direction in regular graphs
• Weak sense of direction labelings and graph embeddings

This page was built for publication: Minimal Chordal Sense of Direction and Circulant Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5756720)