Partições Convexas Geodésicas e Contornos em Grafos
Autores
|
4794 |
1888,6,2018
|
|
|
4795 |
1888,6,2018
|
|
|
4796 |
1888,6,2018
|
Informações:
Publicações do PESC
Seja G um grafo simples e finito. Seja S contido em V(G), seu intervalo fechado I[S] é o conjunto de todos os vértices em algum caminho mínimo entre pares de vértices de S. O conjunto S é convexo se I[S] = S. Dizemos que S é geodésico se I[S] = V(G). O contorno Ct(G) de G é o conjunto formado por vértices v tais que nenhum vizinho de v possui excentricidade maior que v. Nesta tese, definimos o conceito de partição convexa em grafos. Se existe uma partição de V(G) em p conjuntos convexos então G é dito p-convexo. Provamos que é NP-completo decidir se um grafo G é p-convexo para um inteiro fixo p maior ou igual a 2. Demonstramos que todo grafo cordal conexo é p-convexo, para qualquer p em {1, ..., n}. Estabelecemos condições para decidir se uma potência de ciclo é p-convexa. Também desenvolvemos um algoritmo linear para decidir se um cografo é p-convexo. Finalmente, nós consideramos o problema de determinar se o contorno de um grafo conexo G é geodésico. Provamos que se o diâmetro de G é menor ou igual a 4, então Ct(G) é geodésico.
Let G be a finite simple graph. Let S be a subset of V(G), its closed interval I[S] is the set of all vertices lying on a shortest path between any pair of vertices of S. The set $S$ is convex if I[S] = S. We say that S is geodetic if I[S] = V(G). The contour Ct(G) of G is the set formed by vertices v such that no neighbor of v has an eccentricity greater than v. In this thesis, we define the concept of convex partition of graphs. If there exists a partition of V(G) into p convex sets we say that G is p-convex. We prove that is NP-complete to decide whether a graph G is p-convex for a fixed integer p greater than or equal to 2. We show that every connected chordal graph is p-convex, for all p in {1, ..., n}. We establish conditions to decide if a power of cycle is p-convex. We also develop a linear-time algorithm to decide if a cograph is p-convex. Finally, we consider the problem of determining whether the contour of a connected graph G is geodetic. We prove that if the diameter of G is less than or equal to 4, then Ct(G) is geodetic.