Nontraceable detour graphs
type: Item
instance of: scholarly article
title: Nontraceable detour graphs
zbMATH Open document ID: 1113.05052
author: Frank Bullock
author: Marietjie Frick
author: Róbert Vlačuha
author: Gabriel Semanišin
published in: Discrete Mathematics
publication date: 2007-03-02T00:00:00Z
review text: Let \(G\) be a graph with vertex set \(V(G)\). The detour order of a vertex \(v\in V(G)\) is the order of a longest path in \(G\) with initial vertex \(v\), and the detour order of \(G\) is the maximum of the detour orders of its vertices. The detour sequence of \(G\) is a sequence consisting of the detour orders of its vertices. A graph is called a detour graph if its detour sequence is constant. The detour deficiency of a graph \(G\) is the difference between \(| V(G)| \) and its detour order. A graph \(G\) is traceable if its detour order is equal \(| V(G)| \). The authors present a number of constructions for detour graphs of all orders greater than 17 and all detour deficiencies greater than zero. These constructions are used to give examples of nontraceable detour graphs with chromatic number \(k\geq 2\) and girths up to 7. In addition, the authors show that for all integers \(d\geq 1\) and \(k\geq 3\) there exist nontraceable detour graphs with chromatic number \(k\) and detour deficiency \(d\). The paper concludes with some open problems.
reviewed by: Lutz Volkmann
Mathematics Subject Classification ID: 05C38
Mathematics Subject Classification ID: 05C75
zbMATH DE Number: 5130442
zbMATH Keywords: detour order
zbMATH Keywords: detour sequence
zbMATH Keywords: longest path
MaRDI profile type: Publication
full work available at URL: j.disc.2006.07.019
OpenAlex ID: W1993040197
cites work: A survey of hereditary properties of graphs
cites work: Detour Chromatic Numbers
cites work: Smallest claw-free, 2-connected, nontraceable graphs and the construction of maximal nontraceable graphs
cites work: Q3937438
cites work: Smallest maximally nonhamiltonian graphs
cites work: Q4943521
cites work: Q3287781
cites work: On Realizability of a Set of Integers as Degrees of the Vertices of a Linear Graph. I
cites work: A remark on the existence of finite graphs
cites work: On Detours in Graphs1
cites work: Eccentric sequences in graphs
cites work: Degrees in Homogeneously Traceable Graphs
cites work: Q3942985
cites work: Q3710548
cites work: Q3487383
cites work: Q5537559
DOI: 10.1016/J.DISC.2006.07.019
Recommended article: Detours in directed graphs
Recommended article: Q3513959
Recommended article: Q4677953
Recommended article: Q3620765
Recommended article: Detour-saturated graphs
Recommended article: The edge geodetic number and Cartesian product of graphs
Recommended article: Q3734439
Recommended article: Q3567787
Recommended article: Q5267618
Recommended article: Q3565901
description: scientific article; zbMATH DE number 5130442