Просмотр кода страницы K-Path graph

'''<math>k</math>-Path graph''' --- граф <math>k</math>-путей. 

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