Caracterizações de convexidades geométricas de grafos

• Rafael Teixeira de Araújo UFC
• Rudini Menezes Sampaio UFC

DOI: https://doi.org/10.5753/etc.2016.9844

Resumo

Uma convexidade de grafos é geométrica se todo conjunto convexo é o fecho convexo de seus vértices extremos. Vários trabalhos têm caracterizado as classes de grafos para os quais uma dada convexidade é geométrica, como a convexidade monofônica em grafos cordais, a convexidade geodésica em grafos ptolemaicos [Farber and Jamison 1986] e a convexidade m3 em grafos bipolarizados fracos [Dragan et al. 1999]. Nesse artigo, obtemos caracterizações para as convexidades P3, P3 , P+4 e triangle-path. Também obtemos resultados no sentido oposto: dada uma classe de grafos, existe alguma convexidade que só é geométrica nessa classe?

 

Referências

Ara´ujo, R. T., Sampaio, R., and Szwarcfiter, J. (2013). The convexity of induced paths of order three. Electronic Notes in Discrete Mathematics, 44(0):109 – 114.

Ara´ujo, R. T. and Sampaio, R. (2013). Convexidades de caminhos e convexidades geom´etricas. Dissertação de Mestrado (MDCC-UFC), Fortaleza, Brazil.

Campos, V., Sampaio, R. M., Silva, A., and Szwarcfiter, J. L. (2015). Graphs with few P4’s under the convexity of paths of order three. Discrete Applied Mathematics, 192:28– 39. 11th Cologne/Twente Workshop on Graphs and Combinatorial Optimization (CTW 2012).

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

Dourado, M. C., Protti, F., and Szwarcfiter, J. L. (2010). Complexity results related to monophonic convexity. Discrete Applied Mathematics, 158(12):1268 – 1274.

Dragan, F. F., Nicolai, F., and Brandst¨adt, A. (1999). Convexity and HHD-free graphs. SIAM Journal on Discrete Mathematics, 12(1):119–135 (electronic).

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