Minimum chromaticity and efficient domination of circulant graphs
Goran Ružić · Summit (Simon Fraser University) · 2003
Effective solutions to problems encountered in networks are often based on whether the elementary set can be partitioned into classes according to some specific criteria. The chromatic number of a graph G(V,E) is the minimum number of colours needed to colour the vertices of G such that no two adjacent vertices have the same colour. An independent set D of G is called an efficient dominating set of G if every vertex not in D is adjacent to exactly one vertex in D. The circulant graph G = GC(n;S) of order n is a graph on vertex set V= (vO, vl, ..., v ~ ~ } and connection set S (1,2 ,..., 19 with an edge joining vi and vj whenever i= (j + sk) mod n, s k ~ S. In this thesis, we show that many of the circulant graphs which are often proposed as underlying architectures for computer networks are at most three colorable. Moreover, we establish infinite families of GC(n;S), ISI=2 with chromatic number at most 3. We provide a complete characterization of circulant graphs GC(n;S), ISI=2 which admit an efficient dominating set.