Powers of connected graphs and hamiltonicity
type: Item
instance of: scholarly article
title: Powers of connected graphs and hamiltonicity
zbMATH Open document ID: 0547.05042
DOI: 10.1016/0012-365X(84)90106-7
author: N. E. Zubov
published in: Discrete Mathematics
publication date: 1984-01-01T00:00:00Z
review text: A graph G is n-hamiltonian (resp. n-edge hamiltonian) if after the removal of any k vertices (resp. edges) with 0\(\leq k\leq n\), the resulting graph is hamiltonian. The kth power of a graph G is the graph having the same vertex-set as G and such that u and v, vertices of \(G^ k\), are adjacent if and only if the distance between u and v in G is at most k. In this paper the authors prove that if G is a connected graph then \(G^ k\) is (k-2)-edge hamiltonian if \(k\geq 3\) and \(| V(G)|\geq k+1.\) Furthermore, if G is 2-connected and \(| V(G)\geq k+2\) then \(G^ k\) is (k-1)-edge hamiltonian.
Mathematics Subject Classification ID: 05C45
zbMATH DE Number: 3871404
zbMATH Keywords: k-edge Hamiltonian
zbMATH Keywords: power of a graph
reviewed by: R. L. Hemminger
MaRDI profile type: Publication
cites work: Q4141842
cites work: The powers of a connected graph are highly hamiltonian
cites work: The cube of every connected graph is 1-hamiltonian
cites work: In the square of graphs, Hamiltonicity and pancyclicity, Hamiltonian connectedness and panconnectedness are equivalent concepts
cites work: Minimumk-hamiltonian graphs, II
cites work: MinimumK-hamiltonian graphs
full work available at URL: 0012-365x(84)90106-7
OpenAlex ID: W2024832813
description: scientific article; zbMATH DE number 3871404