On the nonplanarity of powers of paths (Q2839690)

The main object of the paper are the \(k\)th powers \(P_n^k\) of a path \(P_n\) of order \(n\). The size of such graphs is \(kn - \binom{k+1}{2}\). The authors observe that for \(n = 1, 2, 3\) such graphs are maximal with respect to the following properties: NEWLINE{\parindent=6mmNEWLINE\begin{itemize}\item[1.]\(P_n^1\) is a tree, and this tree is a maximal forest. NEWLINE\item[2.]\(P_n^2\) is maximal outerplanar. NEWLINE\item[3.]\(P_n^3\) is maximal planar. NEWLINEThe graph \(P_n^k\) is nonplanar for \(k>3\).NEWLINENEWLINE\end{itemize}}NEWLINEA measure of nonplanarity is the crossing number \(\mathrm{cr}(G)\). NEWLINEThe authors calculate the number \(\mathrm{cr}(G)\) for the graphs \(P_n^4\) and \(P_7^5\).NEWLINENEWLINENEWLINEAnother measure of nonplanarity of \(P_n^k\) is the determination of certain graphs \(F\) such that a topological \(F\) is forbidden as a subgraph of \(P_n^k\). In the paper under review two results in this field are established. NEWLINENEWLINENEWLINEThe first one determines conditions under which the graph contains a topological \(K_r\), the second one determines conditions under which the graph contains a topological \(H\). NEWLINENEWLINENEWLINE NEWLINEAll the above results are quite simple. The most interesting questions are posed in Paragraph 4 of the paper. Unfortunately, the authors do not give an answer to any of these questions. NEWLINENEWLINENEWLINENEWLINEReviewer's remark: In my opinion, the paper should not have been published in its present form, the authors should have given the NEWLINEanswer to at least one of the questions stated in Section 4.