Fractal graphs

The lexicographic sum of graphs is defined as follows. Let G be a graph. With each v ∈ V ( G ) associate a graph H v . The lexicographic sum of the graphs H v over G is obtained from G by substituting each v ∈ V ( G ) by H v . Given distinct v , w ∈ V ( G ) , we have all the possible edges in the lexicographic sum between V ( H v ) and V ( H w ) if v w ∈ E ( G ) , and none otherwise. When all the graphs H v are isomorphic to some graph H , the lexicographic sum of the graphs H v over G is called the lexicographic product of H by G and is denoted by G ≀ H . We say that a graph G is fractal if there exists a graph Γ , with at least two vertices, such that G ≃ Γ ≀ G . There is a simple way to construct fractal graphs. Let Γ be a graph with at least two vertices. The graph Γ ω is defined on the set V ( Γ ) ω of functions from ω to V ( Γ ) as follows. Given distinct f , g ∈ V ( Γ ) ω , f g is an edge of Γ ω if f ( m ) g ( m ) is an edge of Γ , where m is the smallest integer such that f ( m ) ≠ g ( m ) . The graph Γ ω is fractal because Γ ≀Γ ω ≃ Γ 1 + ω ≃ Γ ω . We prove that a fractal graph is isomorphic to a lexicographic sum over an induced subgraph of Γ ω , which is itself fractal.