Um Limitante Superior para o Número Geodésico nos Grafos de Kneser
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.
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
Como Citar
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.
