Maximal Digraphs with Respect to Primitive Positive Constructability
Publikation: Beitrag in Fachzeitschrift › Forschungsartikel › Beigetragen › Begutachtung
Beitragende
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
Originalsprache | Englisch |
---|---|
Seiten (von - bis) | 997-1010 |
Seitenumfang | 14 |
Fachzeitschrift | Combinatorica : an international journal on combinatorics and the theory of computing |
Jahrgang | 42 |
Ausgabenummer | 6 |
Publikationsstatus | Veröffentlicht - 2022 |
Peer-Review-Status | Ja |
Externe IDs
Scopus | 85139669718 |
---|---|
ORCID | /0000-0001-8228-3611/work/142241229 |