Hamiltonian iterated line graphs
type: Item
instance of: scholarly article
title: Hamiltonian iterated line graphs
zbMATH Open document ID: 1027.05055
DOI: 10.1016/S0012-365X(01)00442-3
author: Zhanhong Liu
author: Liming Xiong
published in: Discrete Mathematics
publication date: 2002-12-02T00:00:00Z
review text: The Hamiltonian index \(h(G)\) of a connected multigraph \(G\) other than a path is defined as the minimum integer \(n\) such that \(L^n(G)\) is Hamiltonian, where \(L(G)=L^1(G)\) denotes the line graph of \(G\) and \(L^n(G)=L(L^n(G))\). A well-known theorem of \textit{F. Harary} and \textit{C. S. J. A. Nash-Williams} [Can. Math. Bull. 8, 701-709 (1965; Zbl 0136.44704)] says that \(h(G)=1\) iff \(G\) has a Eulerian subgraph \(S\) such that each edge of \(G\) is incident with a vertex of \(S\). In the paper under review, this classical result is extended to a characterization of multigraphs of Hamiltonian index \(n\geq 2\), given in terms of existence of certain Eulerian subgraphs. The main theorem is then used to obtain results that might be helpful when designing an algorithm for finding \(h(G)\). While the problem to determine \(h(G)\) is known to be NP-hard [\textit{A. A. Bertossi}, Inf. Process. Lett. 13, 157-159 (1981; Zbl 0495.68058)] in general, the authors conjecture that it can be solved in polynomial time provided \(h(G)\geq 2\). Another application of the main theorem is an upper bound on \(h(G)\), which implies previously published upper bounds on \(h(G)\) for multigraphs with minimum degree at least three [\textit{G. Chartrand} and \textit{C. E. Wall}, Studia Sci. Math. Hungar. 8(1973), 43-48 (1974; Zbl 0279.05121)] or graphs with maximum degree at least three [\textit{M. L. Saražin}, Discrete Math. 134, 85-91 (1994; Zbl 0815.05044)].
reviewed by: Tomáš Dvořák
Mathematics Subject Classification ID: 05C45
Mathematics Subject Classification ID: 05C35
zbMATH DE Number: 1838935
zbMATH Keywords: iterated line graph
zbMATH Keywords: Eulerian subgraph
zbMATH Keywords: Hamiltonian index
zbMATH Keywords: split block
zbMATH Keywords: contraction of graphs
MaRDI profile type: Publication
description: scientific article; zbMATH DE number 1838935