| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 4652023 | Electronic Notes in Discrete Mathematics | 2013 | 6 Pages |
In this paper, we introduce a new convexity on graphs similar to the well known P3-convexity [R.Barbosa, E.Coelho, M.Dourado, D.Rautenbach, J.L.Szwarcfiter, A.Toman. On the Radon number for P3-convexity, Proc. LATINʼ2012, Lecture Notes in Computer Science 7256 (2012), 267–278], which we will call -convexity. We show that several -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.
