Homomorphism-homogeneous graphs with loops


Andreja Ilić, Dragan Mašulović, Uroš Rajković




In 2006, P. J. Cameron and J. Nešet\~ril introduced the following variant of homogeneity: we say that a structure is homomorphism-homogeneous if every homomorphism between finite substructures of the structure extends to an endomorphism of the structure. In this paper we classify finite homomorphism-homogeneous graphs where some vertices may have loops, but only up to a certain point. We focus on disconnected graphs, and on connected graphs whose subgraph induced by loops is disconnected. In a way, this is the best one can hope for, since it was shown in a recent paper by M. Rusinov and P. Schweitzer that there is no polynomially computable characterization of finite homomorphism-homogeneous graphs whose subgraph induced by loops is connected (unless P=coNP).