
doi: 10.1007/bf03322213
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.
line graph, clique, Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.), graph-valued function, graph operator, infinite graph
line graph, clique, Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.), graph-valued function, graph operator, infinite graph
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 0 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
