A strongly Hamiltonian-laceable graph is a Hamilton-laceable graph on 
vertices with two bipartition
classes of equal size such that every pair of distinct vertices
in the same bipartition class can be joined by a
path of length 
(Hsieh et al. 2000).
The longest path between distinct vertices therefore has length 
for endpoints in different bipartition
classes and 
for endpoints in the same class. These lengths are maximal
because a path visits each vertex
at most once and alternates between the bipartition classes.
There are 
unordered pairs of vertices
in different bipartition classes and 
pairs in the same class. Consequently, the detour
index of a strongly Hamiltonian-laceable graph 
is
 |
The permutation star graph 
(Hsieh et al. 2000) and the Bruhat
graph 
(Araki and Kikuchi 2007) are strongly Hamiltonian-laceable
for 
.
