Nontraceable detour graphs (Q868352)

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.