Symmetrical path-cycle covers of a graph and polygonal graphs (Q857413)

A graph \(\Gamma\) is called near-polygonal [\textit{M. Perkel}, Ars Comb. 26A, 149--170 (1988; Zbl 0671.05058)] if there is a number \(m\) and a collection \(\mathcal{C}\) of (simple) cycles of length \(m\) in \(\Gamma\) such that every path of length \(2\) in \(\Gamma\) lies on exactly one of the cycles in \(\mathcal{C}\). The graph is called polygonal if \(m\) is equal to the girth of \(\Gamma\). The existence of polygonal and near-polygonal graphs for various values of \(m\) has been considered in, for example, [\textit{M. Perkel} and \textit{C. E. Praeger}, Congr. Numerantium 124, 161--173 (1997; Zbl 0913.05055); \textit{D. Archdeacon} and \textit{M. Perkel}, Congr. Numerantium 70, 81--85 (1990; Zbl 0699.05049)]. The paper under review constructs near-polygonal graphs for arbitrary values of \(m\). Indeed, the situation considered is somewhat more general: given a graph \(\Gamma\) and integers \(l,m\), an \((l,m)\)-path-cycle cover (or \((l,m)\)-cover) of \(\Gamma\) is a collection \(\mathcal{C}\) of \(m\)-cycles in \(\Gamma\) for which every path of length \(l\) in \(\Gamma\) lies on at least one element of \(\mathcal{C}\). The \((l,m)\)-cover is a regular \(\lambda\)-\((l,m)\)-cover if in fact each \(l\)-path lies on exactly \(\lambda\) of the elements of \(\mathcal{C}\). In particular, a graph \(\Gamma\) is near-polygonal if it admits a regular \(1\)-\((2,m)\)-cover. The authors consider the situation where \(\Gamma\) admits an \((l,m)\)-cover and a group \(G\) of automorphisms which restricts to the full automorphism group on each element of the cover, and is transitive on the cover itself. By investigating the cicumstances under which such a situation is possible (Lemma~1.1), the authors construct an infinite family of near-polygonal graphs \(\Gamma\) for each \(m \geq 5\) (Theorem~1.3). For \(m = 5,6,7\), they are able to describe additional structure of the near-polygonal graphs \(\Gamma\) constructed; for example, if \(m = 5\), then \(\Gamma\) is in fact polygonal.