On the dominating (induced) cycles of iterated line graphs
type: Item
instance of: scholarly article
title: On the dominating (induced) cycles of iterated line graphs
author: Yibin Fang
author: Liming Xiong
published in: Discrete Applied Mathematics
publication date: 2022-12-08T00:00:00Z
review text: 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.
reviewed by: Doost Ali Mojdeh
Mathematics Subject Classification ID: 05C69
Mathematics Subject Classification ID: 05C76
zbMATH DE Number: 7628634
zbMATH Keywords: iterated line graph
zbMATH Keywords: dominating cycle
zbMATH Keywords: dominating induced cycle
MaRDI profile type: Publication
full work available at URL: j.dam.2022.09.025
OpenAlex ID: W4307838003
cites work: Linkability in iterated line graphs
cites work: Q5422499
cites work: The existence of complete cycles in repeated line-graphs
cites work: On Hamiltonian Line-Graphs
cites work: The connectivity of line-graphs
cites work: Hamilton-connected indices of graphs
cites work: Forbidden pairs and the existence of a dominating cycle
cites work: The strong perfect graph theorem
cites work: Q3320425
cites work: The structure and existence of 2-factors in iterated line graphs
cites work: The Planar Hamiltonian Circuit Problem is NP-Complete
cites work: Planarity of iterated line graphs
cites work: On Eulerian and Hamiltonian Graphs and Line Graphs
cites work: \(k\)-ordered hamiltonicity of iterated line graphs
cites work: Connectivity of iterated line graphs
cites work: Iterated line graphs are maximally ordered
cites work: Equivalence of Fleischner's and Thomassen's conjectures
cites work: On the Hamiltonian index
cites work: Q3596136
cites work: Outerplanarity of line graphs and iterated line graphs
cites work: Hamiltonian index is NP-complete
cites work: Q3834095
cites work: Existence of Dlambda-cycles and Dlambda-paths
cites work: Existence of dominating cycles and paths
cites work: The existence of even factors in iterated line graphs
cites work: Hamiltonian iterated line graphs
cites work: Hamiltonian claw-free graphs and \(o\)-heavy graphs involving induced cycles
DOI: 10.1016/J.DAM.2022.09.025
description: scientific article; zbMATH DE number 7628634