Recognizing \(k\)-path graphs (Q1962042): Difference between revisions

A recognition algorithm for \(k\)-path graphs is given for every integer \(k\geq 2\). The \(k\)-path graph \({\mathfrak P}_k(H)\) of an undirected graph \(H\) has all length-\(k\) paths of \(H\) as vertices. Two such vertices are adjacent in \({\mathfrak P}_k(H)\) if their union forms a path or cycle of length \(k+1\) in \(H\), and if the common edges of both paths form a path of length \(k-1\). The class of all graphs \(H\) where the start vertex \(x_0\) of every path \(x_0,x_1,\dots, x_t\) of length less than \(k\) has at least two neighbors outside the path be denoted by \(\Gamma_k\). The graph \({\mathfrak P}_k'(H)\) has also all length-\(k\) paths of \(H\) as vertices, but here two vertices are adjacent whenever the corresponding paths form some length-\((k+1)\) path in \(H\) (they are called strongly adjacent paths). This means that \({\mathfrak P}_k(H)={\mathfrak P}_k(H)\) if there is no cycle of length \(k+1\) in \(H\). Using the notions of a biclique as an inclusion-maximal-induced complete bipartite subgraph and of a polarized graph, the author gives a new characterization of \(k\)-graphs (in Theorem 3), which is a necessary and sufficient condition for a given graph \(G\) to be equal to \({\mathfrak P}_k(H)\). A polarized graph is defined to be a graph \(G= (V,E)\) together with certain sets \(M_1(x)\), \(M_2(x)\) whose union equals the neighborhood \(N_G(x)\), for every \(x\in V\). By this characterization the author finds algorithms for polarized \({\mathfrak P}_k\)- and \({\mathfrak P}_k'\)-graph recognition \((\Gamma)\) and he also explains the advantages of applying polarized graphs (algorithm 1 and algorithm 2). By the application of algorithm 2 the author finds all graphs \(H\in\Gamma\) such that \(G={\mathfrak P}_k(H)\) for a given \(G\) (the \(k\)-path graph recognition \((\Gamma)\) which is described by algorithm 3), and he proves that algorithm 3 is correct (in the \(\Gamma= \Gamma_k\)-variant, the running time is \(O(|V|^4)\), and there is at most one such \(H\in\Gamma_k\)). Finally, by algorithm 4, the problem to find all pairs \(k\geq 2\) and \(H\in\Gamma_k\) for a given graph \(G\) such that \(G={\mathfrak P}_k(H)\) is treated, and it is shown that algorithm 4 is correct with running time \(O(|V|^4)\) (Theorem 11). And in this way also an extension of a known uniqueness result is obtained (Theorem 12).