On finite reflexive homomorphism-homogeneous binary relational systems

Dragan Maulovi, Rajko Nenadov, Nemanja Kori

Research output: Contribution to journalArticleResearchpeer-review

7 Citations (Scopus)

Abstract

A structure is called homogeneous if every isomorphism between finitely induced substructures of the structure extends to an automorphism of the structure. Recently, P. J. Cameron and J. Neetil introduced a relaxed version of homogeneity: we say that a structure is homomorphism-homogeneous if every homomorphism between finitely induced substructures of the structure extends to an endomorphism of the structure. In this paper, we consider finite homomorphism-homogeneous relational systems with one reflexive binary relation. We show that for a large part of such relational systems (bidirectionally connected digraphs; a digraph is bidirectionally connected if each of its connected components can be traversed by ⇄-paths) the problem of deciding whether the system is homomorphism-homogeneous is coNP-complete. Consequently, for this class of relational systems there is no polynomially computable characterization (unless P=NP). On the other hand, in case of bidirectionally disconnected digraphs we present the full characterization. Our main result states that if a digraph is bidirectionally disconnected, then it is homomorphism-homogeneous if and only if it is either a finite homomorphism-homogeneous quasiorder, or an inflation of a homomorphism- homogeneous digraph with involution (a specific class of digraphs introduced later in the paper), or an inflation of a digraph whose only connected components are C3° and 1°.

Original languageEnglish
Pages (from-to)2543-2555
Number of pages13
JournalDiscrete Mathematics
Volume311
Issue number21
DOIs
Publication statusPublished - 6 Nov 2011
Externally publishedYes

Keywords

  • Finite digraphs
  • Homomorphism-homogeneous structures

Cite this