On finite reflexive homomorphism-homogeneous binary relational systems

DOI10.1016/J.DISC.2011.07.032MaRDI QIDQ409366zbMATH OpenOpenAlexFDO

Authors Dragan Mašulović, Rajko Nenadov, Nemanja Škorić

Publication date 13 April 2012

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0912.4978

zbMATH Keywords

coNP-completenessfinite digraphshomomorphism-homogeneous relational structures

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Relational systems, laws of composition (08A02) Automorphisms and endomorphisms of algebraic structures (08A35)

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. Nev{s}etv{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 $ightleftarrows$-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^{c}irc$ and $1^{c}irc$.

Recommendations

• Towards finite homomorphism-homogeneous relational structures
• Finite irreflexive homomorphism-homogeneous binary relational systems
• On the complexity of deciding homomorphism-homogeneity for finite algebras
• Connected-homomorphism-homogeneous graphs
• Homomorphism-Homogeneous Relational Structures

Cites work

• Finite homomorphism-homogeneous tournaments with loops
• Finite irreflexive homomorphism-homogeneous binary relational systems
• Homomorphism-Homogeneous Relational Structures
• Homomorphism-homogeneous graphs
• Homomorphism-homogeneous partially ordered sets
• On Subtournaments of a Tournament
• Posets, homomorphisms and homogeneity
• The classification of countable homogeneous directed graphs and countable homogeneous 𝑛-tournaments

Cited in

(12)

• Connected-homomorphism-homogeneous graphs
• On the complexity of deciding homomorphism-homogeneity for finite algebras
• Towards finite homomorphism-homogeneous relational structures
• scientific article; zbMATH DE number 5978026 (Why is no real title available?)
• Towards the classification of polymorphism-homogeneous metric spaces
• On polymorphism-homogeneous relational structures and their clones.
• Homomorphically full reflexive graphs and digraphs
• Finite irreflexive homomorphism-homogeneous binary relational systems
• On a power of $n$-ary relational systems carried by strong homomorphisms
• Towards the characterization of finite homomorphism-homogeneous oriented graphs with loops
• Relational systems with trivial endomorphisms and polymorphisms
• On countable stable structures which are homogeneous for a finite relational language

This page was built for publication: On finite reflexive homomorphism-homogeneous binary relational systems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q409366)