THE MONOID AND GROUP OF COPYING GRAPHS

Abstract. Recently proposed models of self-organizing networks like the web graph often incorporate some form of vertex copying in their design. The infinite limits of graphs generated by these models are almost surely isomorphic to the copying graphs, which are characterized by graph foldings and local versions of adjacency properties satisfied by the infinite random graph. Each finite con-nected graph H gives rise to an infinite copying graph RH. We study the endomorphisms and automorphisms of copying graphs. We prove that the natural order on the retracts of copy-ing graphs embed all countable orders, while the endomorphism monoid of RH is simple and embeds all countable semigroups. We consider which isomorphisms between finite induced subgraphs of RH extend to automorphisms, and prove that all countable groups embed in the automorphism groups of copying graphs. The iso-morphism types of the graphs RH are related to the folding order on finite graphs. We study combinatorial properties of the folding order and prove that it embeds all finite orders. 1