Self-Similar Graphs

Abstract

For any graph $G$ on $n$ vertices and for any {\em symmetric} subgraph $J$ of $K_{n,n}$, we construct an infinite sequence of graphs based on the pair $(G,J)$. The First graph in the sequence is $G$, then at each stage replacing every vertex of the previous graph by a copy of $G$ and every edge of the previous graph by a copy of $J$ the new graph is constructed. We call these graphs {\em self-similar} graphs. We are interested in delineating those pairs $(G,J)$ for which the chromatic numbers of the graphs in the sequence are bounded. Here we have some partial results. When $G$ is a complete graph and $J$ is a special matching we show that every graph in the resulting sequence is an {\em expander} graph.

13 pages, 1 table

Cited by in corpus (10)

• The ideal structures of self-similar $k$-graph C*-algebras
• Zappa-Szép product of a Fell bundle and a groupoid
• Left regular representations of Garside categories II. Finiteness properties of topological full groups
• On the Simplicity of C${}^{\ast }$-algebras Associated to Multispinal Groups
• The homology of the groupoid of the self-similar dihedral group
• A dichotomy for simple self-similar graph $C^{\ast }$-algebras
• Quotients of the Booleanization of an inverse semigroup
• The Jacobson topology of the primitive ideal space of self-similar k-graph C*-algebras
• Remarks On the K-theory of C*-Algebras of Products of Odometers
• Skew products of finitely aligned left cancellative small categories and Cuntz-Krieger algebras