On the dominating (induced) cycles of iterated line graphs (Q2104921)

Let \(G=(V(G), E(G))\) be a graph with vertex set \(V (G)\) and edge set \(E(G)\). Let \(L(G)\) be the line graph of \(G\). The \(i\)-iterated line graph \(L^i(G)\) is defined recursively by \(L^0(G) = G\), \(L^1(G) = L(G)\) and \(L^i(G) = L(L^{i-1}(G))\), and \(L^{i-1}(G)\) is assumed to be nonempty. A cycle \(C\) of a graph \(G\) is dominating if \(G-V(C)\) is edgeless. Let \(H\) be a subgraph of \(G\) and \(e\in G\). Then \(d_G(e,H)=\min\{d_G(e, f): f\in E(H)\}\). If \(d_G(e, H) = 0\) for an edge \(e\) of \(G\), we say that \(H\) dominates \(e\). A subgraph \(H\) of \(G\) is called dominating if it dominates all edges of \(G\). An Eulerian subgraph \(D\) of a graph \(G\) is called a \(D_{\lambda}\)-Eulerian subgraph if every component of \(G-V(D)\) has order less than \(\lambda\). Moreover, if \(D\) is a cycle such that every component of \(G-V(D)\) has order less than \(\lambda\), we call it a \(D_{\lambda}\)-cycle of \(G\). The main results of the paper are as follows. 1. Let \(G\) be a connected simple graph that is not a path. Then \(L(G)\) has a dominating cycle if and only if \(G\) has a \(D_3\)-Eulerian subgraph. 2. Let \(G\) be a connected graph with at least three edges and \(i \ge 2\). Then \(L^i(G)\) has a dominating cycle if and only if \(EDU_i(G) \ne \emptyset\). 3. Let \(G\) be a connected graph and \(k \ge 1\) be an integer. Then \(EDU_k(L(G)) \ne \emptyset\) if and only if \(EDU_{k+1}(G)\ne \emptyset\) . 4. Let \(G\) be a connected graph with at least three edges. Then \(L^2(G)\) has a dominating cycle if and only if \(EDU_2(G) \ne \emptyset\). 5. Let \(H\) be a cubic graph and \(H^\ast\) be the graph obtained from \(H\) by subdividing each edge of \(H\) once. Then \(L^2(H^\ast)\) has a dominating induced cycle if and only if \(H\) is Hamiltonian. 6. It is NP-complete to decide whether a given graph, particularly, a \(2\)-iterated line graph, has a dominating induced cycle.