The Geodesic Carathéodory Number
Resumo
Do teorema de Carathéodory surge a definição do número de Carathéodory para grafos. Este número é bem conhecido nas convexidades monofônica e de caminho de triângulos. Ele é limitado para algumas classes de grafos nas convexidades P3 e geodésica, mas apenas na convexidade P3 sabe-se que ele é ilimitado. Neste artigo, nós provamos que o número de Carathéodory é ilimitado na convexidade geodésica.
Referências
Carath´eodory, C. (1911). Uber den variabilit¨atsbereich der fourierschen konstanten von positiven harmonischen funktionen. In Rend. Circ. Mat. Palermo, pages 193 – 217.
Changat, M. and Mathew, J. (1999). On triangle path convexity in graphs. In Discrete Math, pages 91–95.
D.B. Parker, R. W. and Wolf, M. (2008). On two-path convexity in multipartite tournaments. In European J. Combin., pages 641–651.
Duchet, P. (1988). Convex sets in graphs ii. minimal path convexity. In J. Combin Theory, Ser. B, pages 307–316.
E. M. M. Coelho, M.C. Dourado, D. R. and Szwarcfiter, J. (2013). The carath´eodory number of the p3 convexity of chordal graphs. In The Seventh European Conference on Combinatorics, Graph Theory and Applications, pages 209–214.
M.C. Dourado, D. Rautenbach, e. a. (2013). On the carath´eodory number of interval and graph convexities. In Theoretical Computer Science, pages 127–135.
Changat, M. and Mathew, J. (1999). On triangle path convexity in graphs. In Discrete Math, pages 91–95.
D.B. Parker, R. W. and Wolf, M. (2008). On two-path convexity in multipartite tournaments. In European J. Combin., pages 641–651.
Duchet, P. (1988). Convex sets in graphs ii. minimal path convexity. In J. Combin Theory, Ser. B, pages 307–316.
E. M. M. Coelho, M.C. Dourado, D. R. and Szwarcfiter, J. (2013). The carath´eodory number of the p3 convexity of chordal graphs. In The Seventh European Conference on Combinatorics, Graph Theory and Applications, pages 209–214.
M.C. Dourado, D. Rautenbach, e. a. (2013). On the carath´eodory number of interval and graph convexities. In Theoretical Computer Science, pages 127–135.
Publicado
04/07/2016
Como Citar
LIRA, Eduardo S.; CASTONGUAY, Diane; COELHO, Erika M. M.; COELHO, Hebert.
The Geodesic Carathéodory Number. In: ENCONTRO DE TEORIA DA COMPUTAÇÃO (ETC), 1. , 2016, Porto Alegre.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2016
.
p. 872-874.
ISSN 2595-6116.
DOI: https://doi.org/10.5753/etc.2016.9848.
