Characterisation of regular graphs as loop graphs

From MaRDI portal





Let \((A,\star)\) be a groupoid; a set endowed with a binary operation. A groupoid \((A,\star)\) is a quasi-group if for all \(a,b \in A\) there is unique solution \(x,y\) to the equations \( a \star x = b \) and \( y \star a = b \). A quasi-group with an identity is called a loop. Given a groupoid \((A,\star)\) with a special set \( S \subseteq A \) satisfying the properties of a Cayley set defined in the paper, one can define a groupoid graph GG\((A,S)\) whose vertices are the elements of \(A\) and edges are pairs of the form \( \{ a,as \} \), \(a \in A, s \in S\). If \(A\) is a left quasi-group, GG\((A,S)\) is necessarily regular. Conversely, every finite regular graph \(G\) is shown to be isomorphic to a groupoid graph GG\((A,S)\) where \(A\) is a loop. The multiplication in the loop \(A\) is constructed from \(1\)-regular directed spanning subgraph decompositions of the graph \(G\) and its complement \( \overline{G} \) and a (randomly chosen) base graph \(u\). The structure of the loop \(A\) is then shown to be independent of the choice of \(u\) up-to isotopy. The problem of ``recovering the underlying loop structure of GG\((A,S)\) is also resolved. The main contribution of this paper lies in the fact that it provides an algebraic structure to the seemingly non-algebraic concept of a regular graph. In addition, the construction is a generalization of the concept of quasi-Cayley graphs of [\textit{G. Gauyacq}, Discrete Appl. Math. 77, 43--58 (1997; Zbl 0881.05057)], which itself is a generalization of the concept of Cayley graph.











This page was built for publication: Characterisation of regular graphs as loop graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5462659)