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.

This page was built for publication: Self-Similar Graphs