PreprintarXiv licencearXiv
On the maximum interval index of a graph
Abstract
For a connected graph P G on n vertices, the interval index is defined by Int(G) = {u,v} subset V(G) (|I(u, v)| - 1), where I(u, v) denotes the set of all vertices lying on a shortest u - v path. It was conjectured that, among all connected graphs on n vertices, the path Pn attains the maximum value of the interval index. In this paper we settle this conjecture, and we prove that the maximum is attained only for Pn, except for n = 4, when the cycle C4 attains the same value. We also prove that, for every n >= 31, the maximum interval index among graphs without pendant vertices equals (n^3 - n)/6 - 2(n - 4) and it is attained by a dumbbell graph, obtained by joining two 4-cycles by a path.
Related
- Bicyclic Graphs with Maximum Complementary Diminished Sombor Index
- Integer linear programming based methods for computing the maximum chordal subgraph of an arbitrary graph
- Corrigendum to "On the Maximum Symmetric Division Deg Index of k-Cyclic Graphs [J. Math. 2022, (2022) \#7783128]"
- Maximum spread of vertex degrees in a simple graph
- Maximum index of unbalanced signed graphs without a positive odd cycle
BibTeX
@misc{knor2026maximum,
title = {{On the maximum interval index of a graph}},
author = {Martin Knor and Jelena Sedlar and Riste škrekovski},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.39966},
eprint = {2610.39966},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.39966},
}
RIS
TY - UNPB
TI - On the maximum interval index of a graph
AU - Martin Knor
AU - Jelena Sedlar
AU - Riste škrekovski
PY - 2026
DA - 2026/10/29
PB - arXiv
DO - 10.48550/arxiv.2610.39966
UR - https://arxiv.org/abs/2610.39966
AB - For a connected graph P G on n vertices, the interval index is defined by Int(G) = {u,v} subset V(G) (|I(u, v)| - 1), where I(u, v) denotes the set of all vertices lying on a shortest u - v path. It was conjectured that, among all connected graphs on n vertices, the path Pn attains the maximum value of the interval index. In this paper we settle this conjecture, and we prove that the maximum is attained only for Pn, except for n = 4, when the cycle C4 attains the same value. We also prove that, for every n >= 31, the maximum interval index among graphs without pendant vertices equals (n^3 - n)/6 - 2(n - 4) and it is attained by a dumbbell graph, obtained by joining two 4-cycles by a path.
ER -