Maximal partial clones determined by the areflexive relations
type: Item
instance of: scholarly article
title: Maximal partial clones determined by the areflexive relations
zbMATH Open document ID: 0695.08010
DOI: 10.1016/0166-218X(92)90279-J
author: Lucien Haddad
author: Ivo G. Rosenberg
published in: Discrete Applied Mathematics
publication date: 1989-01-01T00:00:00Z
review text: This paper studies completeness or primality for partial algebras on a finite universe \({\mathfrak k}=\{0,1,...,k-1\}\). A universal completeness criterion reduces to finding the complete list of maximal partial clones. The authors describe all these clones for \(k\geq 3\) relating them to areflexive h-ary relations admitting a strong h-colouring. For a binary relation \(\rho\), this yields two cases: (a) if \(\rho\) is symmetric (i.e. a graph), then it determines a maximal partial clone iff \(\rho\) is bipartite; (b) if \(\rho\) is asymmetric, then it determines a maximal partial clone iff \(\rho\) is a directed graph without two consecutive arcs.
Mathematics Subject Classification ID: 08A40
Mathematics Subject Classification ID: 08A55
Mathematics Subject Classification ID: 05C15
zbMATH DE Number: 4137845
zbMATH Keywords: complete clones
zbMATH Keywords: bipartite graph
zbMATH Keywords: primality
zbMATH Keywords: maximal partial clones
zbMATH Keywords: directed graph
reviewed by: Raffaella Franci
MaRDI profile type: Publication
cites work: The strong chromatic number of partial triple systems
cites work: Q5596738
cites work: Q4198056
cites work: Q4726313
cites work: Q3816130
cites work: Q5832049
cites work: Q3208654
cites work: Maximal subalgebras of algebras of partial multivalued logic functions
cites work: Q5519922
cites work: Q4657021
cites work: Q3666907
cites work: Q4014307
description: scientific article; zbMATH DE number 4137845