On finite reflexive homomorphism-homogeneous binary relational systems

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šetřil introduced a relaxed version of homogeneity: we say that a structure is homomorphism-homogeneous if ever...

Full description

Saved in:
Bibliographic Details
Published in:Discrete mathematics 2011-11, Vol.311 (21), p.2543-2555
Main Authors: Mašulović, Dragan, Nenadov, Rajko, Škorić, Nemanja
Format: Article
Language:English
Subjects:
Algebra
Automotive components
Binary systems
Combinatorics
Combinatorics. Ordered structures
Disengaging
Exact sciences and technology
Finite digraphs
Functional analysis
Graph theory
Homomorphism-homogeneous structures
Inflation
Mathematical analysis
Mathematics
Sciences and techniques of general use
Substructures
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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šetř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 ⇄-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∘.
ISSN:0012-365X
1872-681X
DOI:10.1016/j.disc.2011.07.032