Valid Path Numberings in Circulant Graphs

A atribuição de rótulos aos vértices e/ou arestas de um dado grafo G = (V, E), respei-
tando-se condições pré-definidas, é um problema bem conhecido da área de Teoria de Grafos. A rotulagem de um grafo G, de ordem n, é definida como numeração quando o conjunto de inteiros {1, . . . , n} é usado para rotular V(G) de maneira distinta. Um caminho com três vértices é considerado válido se o rótulo associado ao seu vértice central for menor que os rótulos associados aos vértices nos extremos do caminho. O Problema dos Caminhos Válidos envolve encontrar uma numeração que otimize o número de caminhos válidos em G. O foco deste trabalho é a classe de grafos circulantes e, em particular, duas subclasses denominadas grafos circulantes prefixais e grafos circulantes sufixais, para as quais são definidas uma numeração específica πI e a quantidade de caminhos válidos induzidos por πI . A quantidade de caminhos válidos induzida por πI é provada ser mínima em grafos circulantes prefixais e máxima em grafos circulantes sufixais. Um algoritmo para realizar tal numeração em grafos de quaisquer classes também é proposto.