Infinite \(\Phi\)-periodic graphs (Q1911989): Difference between revisions

Let \(\Phi\) be any graph-valued function (a simple example is the well-known function \({\mathcal L}: G\to {\mathcal L}G\) which arranges to every graph \(G\) its line graph \({\mathcal L}G\)). A graph \(G\) is \(\Phi\)-periodic if there is an integer \(p>0\) such that \(G\) and \(\Phi^pG\) are isomorphic. A graph \(G\) is \(\Phi\)-fixed if \(G\) and \(\Phi G\) are isomorphic. It is shown how to construct \(\Phi\)-periodic graphs provided the function \(\Phi\) fulfills certain axioms. A key to the given construction is a direct limit graph of the following sequence of graphs: \[ S: G_0\subseteq^{f_0}G_1\subseteq^{f_1}G_2\subseteq^{f_2} G_4\subseteq^{f_4}G_8\dots, \] where e.g. \(f_0\) denotes a monomorphism from \(G_0\) into \(G_1\) and analogous for the other functions \(f_1,f_2,f_4,\dots\). The author brings some applications of this construction. E.g.: For every \(k\)-line function \({\mathcal L}_k\) and every infinite cardinal number \(\aleph\) there is some \({\mathcal L}_k\)-fixed graph containing \(K_{\aleph}\). (The vertices of a \(k\)-line graph \({\mathcal L}_kG\) are complete subgraphs with \(k\) vertices in \(G\).) For every infinite cardinal number \(\aleph\) there is some \({\mathcal L}_3\)-fixed graph inside the class \(\Gamma_{\aleph}\) of graphs \(G\) with the following properties: (1) every edge lies in some \(K_{\aleph}\); (2) every clique has size at least 4; and (3) \({\mathcal L}_3G\) is connected. The construction is also applied to the \(k\)-path graph operator and to the Gallai graph operator.