On the maximum interval index of a graph
Martin Knor, Jelena Sedlar, Riste škrekovski
Source 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.
Evidence graph
No public relationships recorded yet.
Integrity note: This page is a factual metadata record created by deterministic ingestion. It is not a claim that the work moves a mathematical frontier or has been independently verified.