Fisher, David C.; Spalding, Anne Domination of circulant graphs: An example of min-plus algebra. (English) Zbl 0898.05032 Congr. Numerantium 128, 45-54 (1997). 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. Reviewer: W.G.Brown (Montreal) Cited in 1 Document 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 Keywords:precedence digraph; precedence matrix; eigenvalue; eigenvector; circulant graph; domination number; min-plus algebra Citations:Zbl 0824.93003 PDFBibTeX XMLCite \textit{D. C. Fisher} and \textit{A. Spalding}, Congr. Numerantium 128, 45--54 (1997; Zbl 0898.05032)