The detour index
of a connected graph
is a graph invariant defined
as half the sum of all off-diagonal matrix
elements of the detour matrix of
.
Unless otherwise stated, hydrogen atoms are usually ignored in the computation of such indices as organic chemists usually do when they write a benzene ring as a hexagon (Devillers and Balaban 1999, p. 25).
Precomputed detour indices for many named graphs are available in the Wolfram Language as GraphData[graph, "DetourIndex"].
Since a Hamilton-connected graph with vertex count has all off-diagonal matrix elements
equal to
, the detour index of such a graph
is given by
.
For a strongly Hamiltonian-laceable graph
with two bipartition classes of size
,
the longest path has length
between endpoints in different classes and
between distinct endpoints in the same class. There are
unordered pairs of the first kind
and
of the second, giving
|
(1)
|
This applies to the permutation star graph and the Bruhat
graph
with
for
(Hsieh et al. 2000, Araki
and Kikuchi 2007).
For the complete bipartite graph with positive part sizes, put
. Its detour index is
when
and
otherwise.
More generally, for a complete multipartite graph with at least three nonempty parts, let be its vertex count,
its largest part size, and
. Counting endpoint pairs in its detour
matrix gives
|
(2)
|
The detour index is not particularly good at distinguishing graphs. The figures above illustrate a number of small nonisomorphic graphs sharing the same detour index (Amić and Trinajstić 1995; Nikolić et
al. 2000, p. 292, corrected), where
is the number of graph vertices.
The following table gives values for various common classes of graphs. The index of each value list in the table starts at 1. An X indicates that the family
in that row is not defined for the corresponding parameter value or that its detour
index is undefined because the graph is disconnected.
The -crossed
prism graph has
vertices for
, so its first defined value
occurs at
.
| graph | OEIS | sequence |
| Andrásfai graph | A386906 | 1, 35, 196, 550, 1183, 2176, 3610, 5566, 8125, ... |
| antiprism graph | A139757 | X, X, 75, 196, 405, 726, 1183, 1800, 2601, 3610, ... |
| Apollonian network | A297027 | 18, 126, 1575, ... |
| barbell graph | A226450 | X, X, 45, 124, 265, 486, 805, 1240, 1809, ... |
| black bishop graph | A387645 | 0, 1, 28, 194, 936, 2601, 7200, 15376, 32800, ... |
| book graph | A387659 | 16, 67, 150, 251, 378, 531, 710, 915, ... |
| Bruhat graph | A296782 | 0, 1, 63, 6216, 846120, 185976720, ... |
| cocktail party graph | A139757 | X, 16, 75, 196, 405, 726, 1183, 1800, 2601, ... |
| complete bipartite graph | A296819 | 1, 16, 69, 184, 385, 696, 1141, 1744, 2529, 3520, ... |
| complete graph | A002411 | 0, 1, 6, 18, 40, 75, 126, 196, 288, 405, 550, ... |
| complete tripartite graph | A002411 | 6, 75, 288, 726, 1470, 2601, ... |
| X, 184, 696, 1744, 3520, 6216, 10024, ... | ||
| crown graph | X, X, 63, 184, 385, 696, 1141, 1744, 2529, 3520, ... | |
| cube-connected cycle graph | A296777 | X, X, 6348, 126016, 2022480, ... |
| cycle graph | X, X, 6, 16, 35, 63, 105, 160, 234, 325, 440, 576, ... | |
| Fibonacci cube graph | A291918 | 1, 4, 28, 174, 864, 4000, 18241, ... |
| folded cube graph | A296778 | X, 1, 18, 184, 1800, 15136, ... |
| gear graph | A033430 | X, X, 108, 256, 500, 864, 1372, 2048, 2916, 4000, ... |
| grid graph | A296779 | 0, 16, 256, 1744, 6912, 21744, ... |
| grid graph | A296780 | 0, 184, 8788, ... |
| halved cube graph | A002411 | 0, 1, 18, 196, 1800, 15376, ... |
| Hanoi graph | 6, 252, 8439, ... | |
| helm graph | A181617 | X, X, 72, 160, 300, 504, 784, 1152, 1620, 2200, ... |
| hypercube graph | A288720 | 1, 16, 184, 1744, 15136, ... |
| Keller graph | X, 1800, 127008, 8323200, ... | |
| king
graph | A288959 | X, 18, 288, 1800, 7200, 22050, ... |
| knight
graph | A296781 | X, X, X, 1532, 6840, 21744, ... |
| ladder
graph | 1, 16, 67, 176, 369, 668, 1099, 1684, 2449, 3416, ... | |
| Menger sponge graph | 2864, ... | |
| Möbius ladder | X, X, 69, 196, 385, 726, 1141, 1800, 2529, 3610, ... | |
| Mycielski
graph | 0, 1, 35, 550, 5566, 49726, 419710, 3447550, ... | |
| odd graph | 0, 6, 390, 20230, 984375, 49092351, 2523571050, ... | |
| pan graph | X, X, 13, 28, 54, 90, 142, 208, 295, 400, 531, 684, ... | |
| path
graph | A000292 | 0, 1, 4, 10, 20, 35, 56, 84, 120, 165, 220, 286, 364, ... |
| permutation star graph | A296782 | 0, 1, 63, 6216, 846120, 185976720, ... |
| prism graph | X, X, 75, 184, 405, 696, 1183, 1744, 2601, 3520, 4851, ... | |
| queen graph | A288959 | X, 18, 288, 1800, 7200, 22050, 56448, 127008, 259200, ... |
| rook complement graph | A288959 | 0, X, 288, 1800, 7200, 22050, 56448, 127008, 259200, ... |
| rook graph | A288959 | 0, 16, 288, 1800, 7200, 22050, 56448, 127008, 259200, ... |
| Sierpiński carpet graph | 160, 123080, ... | |
| Sierpiński gasket graph | A296783 | 6, 69, 1404, 34485, ... |
| Sierpiński tetrahedron graph | 18, 405, 18513, 1081665, 67634433, 4303361025, ... | |
| star
graph | A000290 | 0, 1, 4, 9, 16, 25, 36, 49, 64, 81, 100, 121, 144, ... |
| sun graph | X, X, 69, 180, 375, 678, 1113, 1704, 2475, 3450, ... | |
| sunlet graph | X, X, 39, 92, 185, 318, 511, 760, 1089, 1490, 1991, ... | |
| tetrahedral Johnson graph | X, X, X, X, X, 3610, 20230, 84700, 289338, ... | |
| torus grid graph | A296784 | X, X, 288, 1744, 7200, 21744, 56448, ... |
| transposition graph | A296785 | 0, 1, 69, 6216, ... |
| triangular graph | X, X, 6, 75, 405, 1470, 4200, 10206, 22050, ... | |
| triangular
grid graph | A288719 | 6, 69, 399, 1467, 4197, 10203, 22047, ... |
| web graph | X, X, 189, 452, 970, 1653, 2779, 4080, 6048, 8165, ... | |
| wheel graph | A002411 | X, X, X, 18, 40, 75, 126, 196, 288, 405, 550, 726, ... |
| white bishop graph | X, 1, 16, 194, 726, 2601, 6348, 15376, 30420, ... |
For the folded cube graph, the parameter gives vertex
count
. It is a Hamilton-connected
graph for odd
and a strongly Hamiltonian-laceable
graph for even
(Hsieh and Kuo 2007).
Closed forms for some of these classes of graphs are summarized in the following table.