Premium
Computational and structural analysis of the contour of graphs
Author(s) -
Artigas Danilo,
Dantas Simone,
Oliveira Alonso L. S.,
Silva Thiago M. D.
Publication year - 2018
Publication title -
international transactions in operational research
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.032
H-Index - 52
eISSN - 1475-3995
pISSN - 0969-6016
DOI - 10.1111/itor.12290
Subject(s) - combinatorics , geodetic datum , mathematics , vertex (graph theory) , bipartite graph , discrete mathematics , shortest path problem , graph , geodesy , geography
Let G = ( V , E ) be a finite, simple, and connected graph. The closed interval I [ S ] of a set S ⊆ V is the set of all vertices lying on a shortest path between any pair of vertices of S . The set S is geodetic if I [ S ] = V . The eccentricity of a vertex v is the number of edges in the greatest shortest path between v and any vertex w of G . A vertex v is a contour vertex if no neighbor of v has eccentricity greater than v . The contour C t ( G ) of G is the set formed by the contour vertices of G . We consider two problems: ( a ) the problem of determining whether the contour of a graph class is geodetic; ( b ) the problem of determining if there exists a graph such that I [ C t ( G ) ] is not geodetic. We obtain a sufficient condition that is useful for both problems; we prove a realization theorem related to problem ( a ) and show two infinite families such that C t ( G ) is not geodetic. Using computational tools, we establish the minimum graphs for which C t ( G ) is not geodetic; and show that all graphs with | V | < 13 , and all bipartite graphs with | V | < 18 , are such that I [ C t ( G ) ] is geodetic.