×

Domination of circulant graphs: An example of min-plus algebra. (English) Zbl 0898.05032

Given a positive integer \(m\), let \(V=[0,1,\dots,n-1]\). For any \(S\subseteq V-\{0\}\), the circulant graph \(C_m[S]\) has vertex set \(V\) and all edges \(ij\) such that \(i-j\in S\) or \(j-i\in S\). This paper is concerned with algorithmic determination of the domination number \(\gamma(C_m[S])\) (the minimum number of vertices which together are adjacent to all other vertices). The “solution” is expressed in the language of the min-plus algebra: on the real numbers extended by \(\infty\), denoted by \({\mathbf R}_+\), the authors, in the spirit of F. L. Baccelli, G. J. Olsder, J.-P. Quadrat, and G. Cohen [Synchronization and linearity. An algebra for discrete event systems (1992; Zbl 0824.93003)] define addition and multiplication respectively by \(a\boxplus b=\min(a,b)\) and \(a\boxtimes b=a+b\); the operations are extended to matrices over \({\mathbf R}_+\), in terms of which powers and trace of square matrices are defined.

MSC:

05C35 Extremal problems in graph theory
05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
05C20 Directed graphs (digraphs), tournaments
68W10 Parallel algorithms in computer science
68R05 Combinatorics in computer science

Citations:

Zbl 0824.93003
PDFBibTeX XMLCite