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

Abstract

A graph convexity is geometric if every convex set is the convex hull of its extreme vertices. Several papers have characterized classes of graphs for which a given convexity is geometric, such as the monophonic convexity in chordal graphs, the geodesic convexity in ptolemaic graphs [Farber and Jamison 1986] and the m3-convexity in weak-biporized graphs [Dragan et al. 1999]. In this paper, we obtain characterizations for the convexities P3, P3 , P+4 and triangle-path. We also obtain results in the opposite direction: is there a graph convexity which is geometric exactly in a given graph class?

 

References

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.