Famílias de grafos com contorno não geodésico

Abstract

 Este trabalho contempla o estudo de conceitos de matemática contínua que podem ser estendidos para matemática discreta, em particular, teoria dos grafos. Um desses conceitos é o de convexidade geodésica. Seja G um grafo, onde V(G) é o conjunto de vértices de G e E(G) é o conjunto de arestas de G. A distância entre dois vértices u e v de G é o número de arestas contidas em um caminho mínimo entre eles. A excentricidade de um vértice u de G é a maior distância entre u e qualquer outro vértice w de G. Um intervalo fechado entre dois vértices u e v de G, denotado por I[u, v], é um subconjunto de V(G) formado por u e v e todos os vértices que se encontram em qualquer caminho mínimo entre u e v. Dado um subconjunto S de V(G), dizemos que S é convexo se I[S]  S. Dizemos que S é geodésico se I[S]  V(G). O contorno de um grafo, Ct(G), é formado pelos vértices cuja excentricidade é maior ou igual a de seus vizinhos. O objetivo deste trabalho é estudar sobre quais condições o contorno é um subconjunto geodésico de G, e contribuir para o estimulante problema em aberto, proposto em 2005 [2], que consiste na seguinte pergunta: “I  2 [Ct(G)]  V(G), para todo G?”. [...]