Um Limitante Superior para o Número Geodésico nos Grafos de Kneser

Esse artigo apresenta uma discussão preliminar sobre o número geodésico nos grafos de Kneser. Dado um grafo G, um conjunto W,W ⊆ V (G), é dito geodesicamente convexo se qualquer vértice em algum caminho mínimo entre u e v está em W, ∀ u, v ∈ W. O processo de detecção desses vértices é chamado de intervalo geodésico de W, denotado por I[W], e o número geodésico de G é o menor tamanho de W ⊆ V (G) tal que I[W] = V (G). Embora o problema de encontrar o número geodésico é reconhecidamente NP-difícil para grafos genéricos, mostramos que existe uma função que limita o número geodésico em grafos de Kneser.