Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
6871461 | Discrete Applied Mathematics | 2018 | 10 Pages |
Abstract
In this paper, we introduce a new convexity on graphs similar to the well known P3-convexity, which we will call P3â-convexity. We show that several P3â-convexity parameters (hull number, convexity number, Carathéodory number, Radon number, interval number and percolation time) are NP-hard even on bipartite graphs. We prove a strong relationship between this convexity and the well known geodesic convexity, which implies several NP-hardness results for the latter. In order to show that, we prove that the hull number for the P3-convexity is NP-hard even for subgraphs of grids and that the convexity number for the P3-convexity is NP-hard even for bipartite graphs with diameter 3. We also obtain linear time algorithms to determine those parameters for the above mentioned convexities for cographs and P4-sparse graphs.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Rafael T. Araújo, Rudini M. Sampaio, VinÃcius F. dos Santos, Jayme L. Szwarcfiter,