Remarks on Hamiltonian properties of powers of digraphs
type: Item
instance of: scholarly article
title: Remarks on Hamiltonian properties of powers of digraphs
zbMATH Open document ID: 0801.05029
DOI: 10.1016/0166-218X(94)90107-4
author: Günter Schaar
published in: Discrete Applied Mathematics
publication date: 1994-11-27T00:00:00Z
full work available at URL: https://eudml.org/doc/18259
review text: The \(k\)th power \(G^ k\) of a digraph \(G\) has the same vertices as \(G\), and there is an arc from \(x\) to \(y\) in \(G^ k\) if there is some directed \(x\)-\(y\) path of length at most \(k\) in \(G\). The present paper deals with Hamiltonian properties of powers of digraphs. In contrast to the situation in the undirected case, where \(G^ 3\) is Hamiltonian connected for every connected graph \(G\) [\textit{M. Sekanina}, Publ. Fac. Univ. Brno 142, 137-140 (1960)], no such result is possible in the directed case. In fact, it is shown that for every positive integer \(k\) there is some strongly connected digraph \(G\) such that \(G^ k\) does not contain any Hamiltonian path. Despite this negative result, some affirmative result is possible for directed cacti---digraphs where for every pair \((x,y)\) of vertices there is exactly one directed \(x\)-\(y\) path. It is proven that the third power \(G^ 3\) of every directed cactus \(G\) is Hamiltonian connected.
reviewed by: Erich Prisner
Mathematics Subject Classification ID: 05C20
Mathematics Subject Classification ID: 05C45
zbMATH DE Number: 612443
zbMATH Keywords: power
zbMATH Keywords: digraph
zbMATH Keywords: Hamiltonian connected
zbMATH Keywords: Hamiltonian path
zbMATH Keywords: directed cacti
MaRDI profile type: Publication
cites work: The square of every two-connected graph is Hamiltonian
cites work: Trees with Hamiltonian square
cites work: Q5728984
Recommended article: On Hamiltonian powers of digraphs
Recommended article: Remarks on Hamiltonian digraphs
Recommended article: Q4726283
Recommended article: Powers of connected graphs and hamiltonicity
Recommended article: Hamiltonian-colored powers of strong digraphs
Recommended article: Q3701451
Recommended article: Powers of Hamiltonian cycles in multipartite graphs
Recommended article: Q5753984
Recommended article: Graph powers and \(k\)-ordered hamiltonicity
Recommended article: The Hamiltonian numbers in digraphs
description: scientific article; zbMATH DE number 612443