Okay, so Steven's right -- there is a (countably infinite) graph which is totally self-similar, called the Rado graph. It's self-similar in the following way: If you partition its vertex set into two (or in general finitely many) parts, and consider the induced subgraph on each of those parts, one of those subgraphs will be isomorphic to the whole graph.
There are two other graphs with this property: the complete graph on countably infinitely many vertices, and the empty graph on countably many vertices. Up to isomorphism, these are the only countable such graphs. (or so Diestel tells me, and the proof actually isn't that hard.)
If you're looking for weaker forms of self-similarity... I'm not sure exactly what it is you want, then. You say something about "transforming nodes into subgraphs that are the same as the larger graph," but there's no reason you can't do something like that with a generic graph. There's a notion of graph product along these lines, where you replace the vertices of a graph by copies of another graph and then connect the new graphs according to the old one. So starting with a graph G, one could certainly construct $G cdot G$, and $G cdot G cdot G$, and so on and so forth... but I don't know if this sequence has a limit (or even in what category that would make sense -- presumably the category of graphs and embeddings, but...)
If you want "looks the same to certain graph invariants," then expander graphs are well worth looking at.
No comments:
Post a Comment