K-Path graph

[math]\displaystyle{ k }[/math]-Path graph --- граф [math]\displaystyle{ k }[/math]-путей.

The [math]\displaystyle{ k }[/math]-path graph [math]\displaystyle{ {\mathcal P}_{k}(H) }[/math] of a graph [math]\displaystyle{ H }[/math] has all length-[math]\displaystyle{ k }[/math] paths of [math]\displaystyle{ H }[/math] as vertices; two such vertices are adjacent in the new graph if their union forms a path or cycle of length [math]\displaystyle{ k+1 }[/math] in [math]\displaystyle{ H }[/math] and if the edge-intersection of both paths forms a path of length [math]\displaystyle{ k-1 }[/math]. It is known that, given a graph [math]\displaystyle{ G = (V,E) }[/math], there is an [math]\displaystyle{ {\mathcal O}(|V|^{4}) }[/math]-time algorithm that decides whether there is some graph [math]\displaystyle{ H }[/math] of minimum degree at least [math]\displaystyle{ k+1 }[/math] with [math]\displaystyle{ G = {\mathcal P}_{k}(H) }[/math].