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 - Dec 2022 |
| Peer-reviewed | Yes |
External IDs
| Scopus | 85139669718 |
|---|---|
| ORCID | /0000-0001-8228-3611/work/142241229 |