Domination in Circulant Graphs

Parallel processing and supercomputing continue to exert great influence in the development of modern science and engineering. The network of processors and interconnections play a vital role in facilitating the communication between processors in a parallel computer. Some of the popular interconnection schemes are rings, toroids and hypercubes. Their popularity stems from the commercial availability of machines with these architectures. These three families of graphs viz., rings, toroids and hypercubes share a common property of being a Cayley graph. Many important problems in networks have been modeled by Cayley graphs. One of the principal issues concerning routing problems is identification of perfect dominating sets in Cayley graphs. Circulant graphs are Cayley graphs constructed on finite cyclic groups. This book deals with domination in circulant graphs in general and some methodologies to determine dominating sets, independent dominating sets, total dominating sets and connected dominating sets in circulant graphs constructed from certain specified generating sets in particular. Domination in directed circulant graph is also dealt with.