On finite reflexive homomorphism-homogeneous binary relational systems (Q409366)

The notion of homomorphism-homogeneity was introduced in [\textit{P. J. Cameron} and \textit{J. Nešetřil}, Comb. Probab. Comput. 15, No. 1--2, 91--103 (2006; Zbl 1091.08001)] as a relaxed version of homogeneity. The aim of this paper is to contribute to the work on the classification of homomorphism-homogeneous relational structures. In particular, the authors consider finite homomorphism-homogeneous relational systems with one reflexive binary relation. Among them are so-called bidirectionally connected digraphs of special interest. It turns out that the problem of deciding their homomorphism-homogeneity is coNP-complete. On the other hand, it is possible to characterize homomorphism-homogenous bidirectionally disconnected digraphs. This characterization is also the main result of this paper.