On Hamiltonian powers of digraphs
type: Item
instance of: scholarly article
title: On Hamiltonian powers of digraphs
zbMATH Open document ID: 0946.05054
author: Antoni Marczyk
published in: Graphs and Combinatorics
publication date: 2000-10-23T00:00:00Z
review text: For a strongly connected digraph \(D\), the \(k\)th power \(D^k\) of \(D\) is the digraph, whose vertex set is the same as \(D\) and whose edge set is such that there is a directed edge from \(x\) to \(y\) in \(D^k\) if the directed distance from \(x\) to \(y\) in \(D\) is less than or equal to \(k\). Ghouila-Houri showed that \(D^k\) is Hamiltonian for every digraph \(D\) on \(n\) vertices and for every \(k\geq n/2\). The present paper characterizes these digraphs \(D\) of odd order, whose \((\lceil n/2\rceil-1)\)th power is Hamiltonian.
reviewed by: Wai-Kai Chen
Mathematics Subject Classification ID: 05C45
Mathematics Subject Classification ID: 05C75
zbMATH DE Number: 1436042
zbMATH Keywords: Hamiltonian digraph
zbMATH Keywords: strongly connected digraph
MaRDI profile type: Publication
full work available at URL: s003730050007
OpenAlex ID: W2027475019
DOI: 10.1007/S003730050007
description: scientific article; zbMATH DE number 1436042