pipette
ENEnglish

On the maximum interval index of a graph

Martin Knor, Jelena Sedlar, Riste \v{s}krekovski

Preprint

En palabras de los autores

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.

Resultado principalEl resumen no menciona limitaciones.

Apareció: viernes, 30 de octubre. arXiv. Preprint, todavía sin revisión por pares.

Comentario de los autores: 16 pages, 0 figures