Algebraic approach to fasciagraphs and rotagraphs (Q1917348)

Let \(G_1, G_2, \dots, G_n\) be a set of arbitrary, mutually disjoint graphs, and let \(X_1, X_2, \dots, X_n\) be a sequence of sets of edges such that an edges of \(X_i\) joins a vertex of \(V(G_i)\) with a vertex of \(V(G_{i + 1 (\text{mod } n)})\). A polygraph \(\Omega_n = \Omega (G_1, G_2, \dots, G_n, X_1, X_2, \dots, X_n)\) is a graph with \[ V (\Omega_n) = V (G_1) \cup V(G_2) \cup \cdots \cup V(G_n) \] and \[ E(\Omega) = E(G_1) \cup X_1 \cup E(G_2) \cup X_2 \cup \cdots \cup E(G_n) \cup X_n. \] If every \(G_i\) is isomorphic to a fixed graph \(G\) and every \(X_i\) is equal to a fixed edge set \(X\), \((1 \leq i \leq n)\), then the polygraph is called a rotagraph denoted by \(\omega_n (G;X)\). A fasciagraph \(\psi_n (G;X)\) is a rotagraph \(\omega_n (G;X)\) without edges between the first and the last copy of a monograph \(G\). In this paper, the authors use an algebraic approach to solve problems on fasciagraphs and rotagraphs. Among others, they show that the domination number of fasciagraphs \(\psi_n (G;X)\) and rotagraphs \(\omega_n (G,X)\) can be computed in \(O (\log n)\) time. This is an improvement over the previously known algorithms for computing the domination number of the grid graph \(P_k \square P_n = \psi_n (P_k; X)\) which were in \(O(n)\) time (for a fixed \(k)\).