Directed Graphclass: adjoint

The following definitions are equivalent:
  1. Let $H=(X,V)$ be a directed graph, possibly with multi-edges. The adjoint $G=(V,U)$ of $H$ has vertex set $V$ and $x\rightarrow y$ is an arc in $G$ iff the terminal endpoint of $x$ in $H$ is the initial endpoint of $y$ in $H$.
    A directed graph $G$ is an adjoint if there is some directed graph $H$ such that $G$ is the adjoint of $H$.
  2. Let $N^+(x)$ be the out-neighbourhood of $x$.
    A directed graph $G$ is an adjoint iff for any two vertices $x,y$ of $G$: If $N^+(x) \cap N^+(y) \neq\emptyset$ then $N^+(x) = N^+(y)$.

References

[90]
C. Berge
Graphs and Hypergraphs
North--Holland, Amsterdam 1985

Related classes

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.

Map

[+]Details

Minimal superclasses

[+]Details

Maximal subclasses

[+]Details

Parameters

Problems

Parameter decomposition

Unweighted problems

Graph canonisation
[?]
Input: A graph G in this class.
Output: A graph C(G) such that C(G) = C(H) iff G is isomorphic to H.
Unknown to ISGCI [+]Details
Graph isomorphism
[?]
Input: Graphs G and H in this class
Output: True iff G and H are isomorphic.
Unknown to ISGCI [+]Details
Hamiltonian cycle
[?]
Input: A graph G in this class.
Output: True iff G has a simple cycle that goes through every vertex of the graph.
Polynomial [+]Details
Hamiltonian path
[?]
Input: A graph G in this class.
Output: True iff G has a simple path that goes through every vertex of the graph.
Unknown to ISGCI [+]Details
Recognition
[?]
Input: A graph G.
Output: True iff G is in this graph class.
Polynomial [+]Details

Weighted problems