Definition:

Let $N^+(x)$ be the out-neighbourhood of $x$.
A directed graph $G$ is a quasi-adjoint iff for any two vertices $x,y$ of $G$: If $N^+(x) \cap N^+(y) \neq\emptyset$ then $N^+(x) \subseteq N^+(y)$ or $N^+(y) \subseteq N^+(x)$, that is, the out-neighborhoods are nested.

;

Inclusions

The map shows the inclusions between the current class and a fixed set of landmark classes. Minimal/maximal is with respect to the contents of ISGCI. Only references for direct inclusions are given. Where no reference is given, check equivalent classes or use the Java application. To check relations other than inclusion (e.g. disjointness) use the Java application, as well.

[+]Details

[+]Details

Problems

Problems in italics have no summary page and are only listed when ISGCI contains a result for the current class.

Unweighted problems

Graph isomorphism Unknown to ISGCI [+]Details
Hamiltonian cycle Polynomial [+]Details
Hamiltonian path Unknown to ISGCI [+]Details
Recognition Polynomial [+]Details