Maximal Digraphs with Respect to Primitive Positive Constructability

Research output: Contribution to journalResearch articleContributedpeer-review

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

Original languageEnglish
Pages (from-to)997-1010
Number of pages14
JournalCombinatorica : an international journal on combinatorics and the theory of computing
Volume42
Issue number6
Publication statusPublished - 2022
Peer-reviewedYes

External IDs

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

Keywords

Library keywords