Fractal graphs

Overview & Synopsis

The lexicographic sum of graphs is defined as follows. Let G be a graph. With each v is an element of 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 is an element of V (G) by H-v. Given distinct v, w is an element of V (G), we have all the possible edges in the lexicographic sum between V (H-v) and V (H-w) if vw is an element of 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 (sic) H. We say that a graph G is fractal if there exists a graph Gamma, with at least two vertices, such that G similar or equal to Gamma (sic) G. There is a simple way to construct fractal graphs. Let Gamma be a graph with at least two vertices. The graph Gamma(omega) is defined on the set V(Gamma)(omega) of functions from omega to V (Gamma) as follows. Given distinct f, g is an element of V (Gamma)(omega), fg is an edge of Gamma(omega) if f (m)g (m) is an edge of Gamma, where m is the smallest integer such that f (m) not equal g (m). The graph Gamma(omega) is fractal because Gamma (sic) Gamma(omega) similar or equal to Gamma(1+omega) similar or equal to Gamma(omega). We prove that a fractal graph is isomorphic to a lexicographic sum over an induced subgraph of Gamma(omega), which is itself fractal.