Directed Graphclass: adjoint ∩ partial directed line

References

[1633]
J. Blazewicz, M. Kasprzak
Reduced-by-matching graphs: toward simplifying Hamiltonian circuit problem
Fundamenta Informatica 118 225-244 (2012)

Equivalent classes

[+]Details

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

Speed

Speed
[?]
The speed of a class $X$ is the function $n \mapsto |X_n|$, where $X_n$ is the set of $n$-vertex labeled graphs in $X$.

Depending on the rate of growths of the speed of the class, ISGCI distinguishes the following values of the parameter:
Constant
Polynomial
Exponential
Factorial
Superfactorial ($2^{o(n^2)}$ )
Superfactorial ($2^{\Theta(n^2)}$ )

unknown [+]Details

Parameters

Problems

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

Parameter decomposition

Unweighted problems

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