On finite reflexive homomorphism-homogeneous binary relational systems

DOI10.1016/J.DISC.2011.07.032zbMATH Open1250.08001arXiv0912.4978OpenAlexW2043054749MaRDI QIDQ409366FDOQ409366

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

Publication date: 13 April 2012

Published in: Discrete Mathematics (Search for Journal in Brave)

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$.

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

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

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)

Cites Work

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

Cited In (9)

• Title not available (Why is that?)
• Connected-Homomorphism-Homogeneous Graphs
• Title not available (Why is that?)
• On polymorphism-homogeneous relational structures and their clones.
• ON THE COMPLEXITY OF DECIDING HOMOMORPHISM-HOMOGENEITY FOR FINITE ALGEBRAS
• 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)