The convexity of induced paths of order three

In this paper, we introduce a new convexity on graphs similar to the well known P 3 -convexity [R.Barbosa, E.Coelho, M.Dourado, D.Rautenbach, J.L.Szwarcfiter, A.Toman. On the Radon number for P 3 -convexity, Proc. LATINʼ2012, Lecture Notes in Computer Science 7256 (2012), 267–278], which we will call P 3 ⁎ -convexity. We show that several P 3 ⁎ -convexity parameters (hull number, convexity number, Carathéodory number, Radon number, interval number and percolation time) are NP-hard even on bipartite graphs. We show a strong relation between this convexity and the well known geodesic convexity [M.Dourado, F.Protti, D.Rautenbach and J.L.Szwarcfiter. Some remarks on the geodetic number of a graph, Discrete Mathematics 310 (2010), 832–837], which implies several NP-hardness results on the geodesic convexity. We also obtain linear time algorithms to determine all those parameters on the above mentioned convexities for some graph classes.