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

From MaRDI portal
scientific article
Language Label Description Also known as
English
On the dominating (induced) cycles of iterated line graphs
scientific article

    Statements

    On the dominating (induced) cycles of iterated line graphs (English)
    0 references
    0 references
    0 references
    8 December 2022
    0 references
    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.
    0 references
    iterated line graph
    0 references
    dominating cycle
    0 references
    dominating induced cycle
    0 references

    Identifiers