On finite reflexive homomorphism-homogeneous binary relational systems

Details On finite reflexive homomorphism-homogeneous binary relational systems On finite reflexive homomorphism-homogeneous binary relational systems

2009-12-25

arxiv.org/abs/0912.4978v1

Mathematics

Combinatorics

Submited to Discrete Mathematics

Scientific paper

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. Ne\v{s}et\v{r}il 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 $\rightleftarrows$-paths) the problem of deciding whether the system is homomorphism-homogeneous is coNP-complete. Consequently, for this class of relational systems we cannot hope for a description involving a catalogue, where by a catalogue we understand a finite list of polynomially decidable classes of structures. 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 peculiar class of digraphs introduced later in the paper), or an inflation of a digraph whose only connected components are $C_3^\circ$ and $\1^\circ$.

Affiliated with

Also associated with

No associations

Rating

On finite reflexive homomorphism-homogeneous binary relational systems does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with On finite reflexive homomorphism-homogeneous binary relational systems, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On finite reflexive homomorphism-homogeneous binary relational systems will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-269795