Read More
Date: 8-3-2022
1423
Date: 20-4-2022
1472
Date: 27-3-2022
1423
|
The detour index of a 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 .
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.
graph | OEIS | sequence |
Andrásfai graph | A000000 | 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 | A000000 | X, X, X, 194, 936, 2601, 7200, 15376, 32800, ... |
book graph | A000000 | 16, 67, 150, 251, 378, 531, 710, 915, ... |
cocktail party graph | A139757 | X, 16, 75, 196, 405, 726, 1183, 1800, 2601, ... |
complete bipartite graph | A000000 | 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 | A000000 | 6, 75, 288, 726, 1470, 2601, ... |
-crossed prism graph | A000000 | X, X, X, 184, 696, 1744, 3520, 6216, 10024, ... |
crown graph | A000000 | X, X, 63, 184, 385, 696, 1141, 1744, 2529, 3520, ... |
cube-connected cycle graph | A296777 | X, X, 6348, 126016, 2022480, ... |
cycle graph | A000000 | 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 | A000000 | 1, 18, 196, 1800, 15376, ... |
Hanoi graph | A000000 | 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 | A000000 | X, 1800, 127008, 8323200, ... |
king graph | A288959 | X, 18, 288, 1800, 7200, 22050, ... |
knight graph | A296781 | X, X, 1532, 6840, 21744, ... |
ladder graph | A000000 | 1, 16, 67, 176, 369, 668, 1099, 1684, 2449, 3416, ... |
Menger sponge graph | A000000 | 2864, ... |
Möbius ladder | A000000 | X, X, 69, 196, 385, 726, 1141, 1800, 2529, 3610, ... |
Mycielski graph | A000000 | 0, 1, 35, 550, 5566, 49726, 419710, 3447550, ... |
odd graph | A000000 | 0, 6, 390, 20230, 984375, 49092351, 2523571050, ... |
pan graph | A000000 | 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, ... |
prism graph | A000000 | 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 | A000000 | 160, 123080, ... |
Sierpiński sieve graph | A296783 | 6, 69, 1404, 34485, ... |
Sierpiński tetrahedron graph | A000000 | ... |
star graph | A000290 | X, X, 4, 9, 16, 25, 36, 49, 64, 81, 100, 121, 144, ... |
sun graph | A000000 | X, X, 69, 180, 375, 678, 1113, 1704, 2475, 3450, ... |
sunlet graph | A000000 | X, X, 39, 92, 185, 318, 511, 760, 1089, 1490, 1991, ... |
tetrahedral graph | A000000 | X, X, X, X, X, 18, 405, 3610, 20230, 84700, 289338, ... |
torus grid graph | A296784 | X, X, 288, 1744, 7200, 21744, 56448, ... |
transposition graph | A296785 | 0, 1, 69, 6216, ... |
triangular graph | A000000 | X, X, 6, 75, 405, 1470, 4200, 10206, 22050, ... |
triangular grid graph | A288719 | 6, 69, 399, 1467, 4197, 10203, 22047, ... |
web graph | A000000 | 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 | A000000 | X, X, X, 194, 726, 2601, 6348, 15376, 30420, ... |
Closed forms for some of these classes of graphs are summarized in the following table.
graph | detour index |
Andrásfai graph | |
antiprism graph | |
barbell graph | |
black bishop graph | |
book graph | |
cocktail party graph | |
complete bipartite graph | |
complete graph | |
complete tripartite graph | |
-crossed prism graph | |
crown graph | |
cycle graph | |
gear graph | |
grid graph | |
grid graph | |
halved cube graph | |
helm graph | |
hypercube graph | |
Keller graph | |
king graph | |
ladder graph | |
Möbius ladder | |
Mycielski graph | |
odd graph | |
pan graph | |
path graph | |
prism graph | |
queen graph | |
rook complement graph | |
rook graph | |
Sierpiński tetrahedron graph | |
star graph | |
sun graph | |
sunlet graph | |
tetrahedral graph | |
torus grid graph | |
transposition graph | |
triangular graph | |
triangular grid graph | |
web graph | |
wheel graph | |
white bishop graph |
Amić, D. and Trinajstić, N. "On the Detour Matrix." Croat. Chem. Acta 68, 53-62, 1995.
Devillers, J. and A. T. Balaban (Eds.). Topological Indices and Related Descriptors in QSAR and QSPR. Amsterdam, Netherlands: Gordon and Breach, pp. 82-83, 2000.
Nikolić, S.; Trinajstić, N.; and Mihalić, A. "The Detour Matrix and the Detour Index." Ch. 6 in Topological Indices and Related Descriptors in QSAR and QSPR (Ed. J. Devillers A. T. and Balaban). Amsterdam, Netherlands: Gordon and Breach, pp. 279-306, 2000.
Randić, M.; DeAlba, L. M.; Harris, F. E. "Graphs with the Same Detour Matrix." Croat. Chem. Acta 71, 53-68, 1998.
Sloane, N. J. A. Sequences A000290/M3556, A000292/M3382, A002411/M4116, and A139757 in "The On-Line Encyclopedia of Integer Sequences."
|
|
5 علامات تحذيرية قد تدل على "مشكل خطير" في الكبد
|
|
|
|
|
لحماية التراث الوطني.. العتبة العباسية تعلن عن ترميم أكثر من 200 وثيقة خلال عام 2024
|
|
|