History

Please fill in your query. A complete syntax description you will find on the General Help page.
Infinite $Φ$-periodic graphs. (English)
Result. Math. 29, No.1-2, 137-148 (1996).
Let $Φ$ be any graph-valued function (a simple example is the well-known function ${\cal L}: G\to {\cal L}G$ which arranges to every graph $G$ its line graph ${\cal L}G$). A graph $G$ is $Φ$-periodic if there is an integer $p>0$ such that $G$ and $Φ^pG$ are isomorphic. A graph $G$ is $Φ$-fixed if $G$ and $ΦG$ are isomorphic. It is shown how to construct $Φ$-periodic graphs provided the function $Φ$ 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 ${\cal L}_k$ and every infinite cardinal number $\aleph$ there is some ${\cal L}_k$-fixed graph containing $K_{\aleph}$. (The vertices of a $k$-line graph ${\cal L}_kG$ are complete subgraphs with $k$ vertices in $G$.) For every infinite cardinal number $\aleph$ there is some ${\cal L}_3$-fixed graph inside the class $Γ_{\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) ${\cal L}_3G$ is connected. The construction is also applied to the $k$-path graph operator and to the Gallai graph operator.
Reviewer: M.Koman (Praha)