Maximal Digraphs with Respect to Primitive Positive Constructability
Research output: Contribution to journal › Research article › Contributed › peer-review
Contributors
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 language | English |
---|---|
Pages (from-to) | 997-1010 |
Number of pages | 14 |
Journal | Combinatorica : an international journal on combinatorics and the theory of computing |
Volume | 42 |
Issue number | 6 |
Publication status | Published - 2022 |
Peer-reviewed | Yes |
External IDs
Scopus | 85139669718 |
---|---|
ORCID | /0000-0001-8228-3611/work/142241229 |