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

  • João V. S. Leite UFF
  • Marcos Bedo UFF
  • Rodolfo A. de Oliveira UFF

Resumo


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.

Palavras-chave: Grafo de Kneser, Convexidade Geodésica, Número Geodésico

Referências

Balogh, J., Cherkashin, D., e Kiselev, S. (2019). Coloring general kneser graphs and hypergraphs via high-discrepancy hypergraphs. Euro. J. Combinatorics, 79:228 – 236.

Berger, M. (1990). Convexity. Amer. Math. Monthly, 97(8):650–701.

Brešar, B. e Valencia-Pabon, M. (2019). Independence number of products of kneser graphs. Discrete Mathematics, 342(4):1017 – 1027.

Cáceres, J., A.Márquez, e Puertas, M. (2008). Steiner distance and convexity in graphs. Eur. J. Comb., 29(3):726–736.

Carathéodory, C. (1911). Über den variabilitätsbereich der fourierschen konstanten von positiven harmonischen funktionen. Rend. Circ. Mat. Palermo, 32:193––217.

Changat, M. e Mathew, J. (1999). On triangle path convexity in graphs. Discrete Mathematics, 206(1):91–95.

Dourado, M. C., Penso, L. D., e Rautenbach, D. (2019). The hull number in the convexity of induced paths of order 3. In Colbourn, C. J., Grossi, R., e Pisanti, N., editors, Combinatorial Algorithms, pages 214–228, Cham. Springer International Publishing.

Dourado, M. C., Protti, F., Rautenbach, D., e Szwarcfiter, J. L. (2010). Some remarks on the geodetic number of a graph. Discrete Mathematics, 310(4):832 – 837.

Duchet, P. (1988). Convex sets in graphs, II. minimal path convexity. Journal of Combinatorial Theory, Series B, 44(3):307 – 316.

Farber, M. e Jamison, R. E. (1986). Convexity in graphs and hypergraphs. SIAM Journal on Algebraic Discrete Methods, 7(3):433–444.

Helly, E. (1923). Ueber mengen konvexer koerper mit gemeinschaftlichen punkter, jahresber. Math. Verein., 32:175––176.

Jin, Z., Wang, F., Wang, H., e Lv, B. (2020). Rainbow triangles in edge-colored kneser graphs. Applied Mathematics and Computation, 365:124724.

Lovász, L. (1978). Kneser’s conjecture, chromatic number, and homotopy. Journal of Combinatorial Theory, Series A, 25(3):319 – 324.

Marcilon, T. e Sampaio, R. (2018). The maximum infection time of the P3 convexity in graphs with bounded maximum degree. Disc. Math., 251:245 – 257.

Mathew, J. K. e Mathew, S. (2018). Monophonic convexity in weighted graphs. Discrete Math., Alg. and Appl., 10(1):1–10.

Pelayo, I. M. (2013). Geodesic Convexity in Graphs. Springer-Verlag New York.

Radon, J. (1921). Mengen konvexer körper, die einen gemeinsamen punkt enthalten. Mathematische Annalen, 83(1–2):113––115.

Valencia-Pabon, M. e Vera, J.-C. (2005). On the diameter of kneser graphs. Discrete Math., 305(1):383 – 385.

Van de Vel, M. (1993). Theory of Convex Structures. North Holland, Amsterdam.
Publicado
30/06/2020
LEITE, João V. S.; BEDO, Marcos; DE OLIVEIRA, Rodolfo A.. Um Limitante Superior para o Número Geodésico nos Grafos de Kneser. In: ENCONTRO DE TEORIA DA COMPUTAÇÃO (ETC), 5. , 2020, Cuiabá. Anais [...]. Porto Alegre: Sociedade Brasileira de Computação, 2020 . p. 9-12. ISSN 2595-6116. DOI: https://doi.org/10.5753/etc.2020.11077.