Computational and structural analysis of the contour of graphs |
| |
| Authors: | Danilo Artigas Simone Dantas Alonso L S Oliveira Thiago M D Silva |
| |
| Affiliation: | 1. Instituto de Ciência e Tecnologia, Universidade Federal Fluminense, Rio das Ostras, RJ, Brazil;2. Instituto de Matemática e Estatística, Universidade Federal Fluminense, Niterói, RJ, Brazil;3. Instituto de Matemática, Pontifícia Universidade Católica do Rio de Janeiro, Rio de Janeiro, RJ, Brazil |
| |
| Abstract: | Let  be a finite, simple, and connected graph. The closed interval  of a set  is the set of all vertices lying on a shortest path between any pair of vertices of S. The set S is geodetic if  . 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  of G is the set formed by the contour vertices of G. We consider two problems:  the problem of determining whether the contour of a graph class is geodetic;  the problem of determining if there exists a graph such that  is not geodetic. We obtain a sufficient condition that is useful for both problems; we prove a realization theorem related to problem  and show two infinite families such that  is not geodetic. Using computational tools, we establish the minimum graphs for which  is not geodetic; and show that all graphs with  , and all bipartite graphs with  , are such that  is geodetic. |
| |
| Keywords: | bipartite graphs contour convexity geodetic set |
|
|
be a finite, simple, and connected graph. The closed interval 
of a set 
is the set of all vertices lying on a shortest path between any pair of vertices of S. The set S is geodetic if 
. 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 
of G is the set formed by the contour vertices of G. We consider two problems: 
the problem of determining whether the contour of a graph class is geodetic; 
the problem of determining if there exists a graph such that 
is not geodetic. We obtain a sufficient condition that is useful for both problems; we prove a realization theorem related to problem 
and show two infinite families such that 
is not geodetic. Using computational tools, we establish the minimum graphs for which 
is not geodetic; and show that all graphs with 
, and all bipartite graphs with 
, are such that 
is geodetic.