Maximal Digraphs with Respect to Primitive Positive Constructability

Publikation: Beitrag in FachzeitschriftForschungsartikelBeigetragenBegutachtung

Abstract

We study the class of all finite directed graphs (digraphs) up to primitive positive constructibility. The resulting order has a unique maximal element, namely the digraph P1 with one vertex and no edges. The digraph P1 has a unique maximal lower bound, namely the digraph P2 with two vertices and one directed edge. Our main result is a complete description of the maximal lower bounds of P2; we call these digraphs submaximal. We show that every digraph that is not equivalent to P1 and P2 is below one of the submaximal digraphs.

Details

OriginalspracheEnglisch
Seiten (von - bis)997-1010
Seitenumfang14
FachzeitschriftCombinatorica : an international journal on combinatorics and the theory of computing
Jahrgang42
Ausgabenummer6
PublikationsstatusVeröffentlicht - Dez. 2022
Peer-Review-StatusJa

Externe IDs

Scopus 85139669718
ORCID /0000-0001-8228-3611/work/142241229

Schlagworte

Bibliotheksschlagworte