Surjective polymorphisms of directed reflexive cycles

DOI10.1007/S00012-023-00834-4MaRDI QIDQ6183437zbMATH OpenFDO

Authors Isabelle Larivière, Benoît Larose, David E. Pazmiño Pullas

Publication date 4 January 2024

Published in Algebra Universalis (Search for Journal in Brave)

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

zbMATH Keywords

constraint satisfaction problemsgeneralized distancesreflexive digraphssurjective polymorphismsSłupecki

Mathematics Subject Classification ID

Distance in graphs (05C12) Directed graphs (digraphs), tournaments (05C20) Paths and cycles (05C38) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Combinatorics on words (68R15)

Abstract: A reflexive cycle is any reflexive digraph whose underlying undirected graph is a cycle. Call a relational structure Slupecki if its surjective polymorphisms are all essentially unary. We prove that all reflexive cycles of girth at least 4 have this property.

Recommendations

• Reflexive digraphs with near unanimity polymorphisms
• Reflexive graphs with near unanimity but no semilattice polymorphisms
• Distributive lattice polymorphisms on reflexive graphs
• NU polymorphisms on reflexive digraphs
• Surjective H-Colouring over Reflexive Digraphs

Cites work

• A discrete homotopy theory for binary reflexive structures
• Algebra and the complexity of digraph CSPs: a survey
• Algebraic properties of crowns and fences
• Function Algebras on Finite Sets
• scientific article; zbMATH DE number 5030273 (Why is no real title available?)
• QCSP on Reflexive Tournaments
• Quantified Constraints in Twenty Seventeen
• Reflexive digraphs with near unanimity polymorphisms
• The clone of operations preserving a cycle with loops
• The complexity of constraint satisfaction games and QCSP
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• Two new homomorphism dualities and lattice operations

Cited in

(1)

• Słupecki digraphs

This page was built for publication: Surjective polymorphisms of directed reflexive cycles

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