2015/03/02 by Mitre C. Dourado, Dourado, Mitre C., Rudini Sampaio +1
Computer Science · Mathematics · #05C99 #Advanced Graph Theory Research #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #Graph theory and applications #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.1503.00458
openalex publication_date 2015/03/02 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A path P = v1, ..., vt is a \em triangle path (respectively, \em monophonic path) of G if no edges exist joining vertices vi and vj of P such that |j - i| > 2; (respectively, |j - i| > 1). A set of vertices S is \em convex in the triangle path convexity (respectively, monophonic convexity) of G if the vertices of every triangle path (respectively, monophonic path) joining two vertices of S are in S. The cardinality of a maximum proper convex set of G is the \em convexity number of G and the cardinality of a minimum set of vertices whose convex hull is V(G) is the \em hull number of G. Our main results are polynomial time algorithms for determining the convexity number and the hull number of a graph in the triangle path convexity.