Abstract | ||
---|---|---|
A set C of vertices of a graph G is P-3-convex if v is an element of C for every path uvw in G with u, w is an element of C. We prove that it is NP-complete to decide for a given graph G and a given integer p whether the vertex set of G can be partitioned into p non-empty disjoint P-3-convex sets. Furthermore, we study such partitions for a variety of graph classes. |
Year | Venue | Keywords |
---|---|---|
2010 | DISCRETE MATHEMATICS AND THEORETICAL COMPUTER SCIENCE | graph convexity,convex partition |
Field | DocType | Volume |
Discrete mathematics,Strength of a graph,Combinatorics,Graph toughness,Bound graph,Graph power,Vertex (graph theory),Cycle graph,Symmetric graph,Mathematics,Complement graph | Journal | 12.0 |
Issue | ISSN | Citations |
5.0 | 1462-7264 | 9 |
PageRank | References | Authors |
0.62 | 9 | 5 |
Name | Order | Citations | PageRank |
---|---|---|---|
Carmen C. Centeno | 1 | 61 | 3.66 |
S. Dantas | 2 | 51 | 5.14 |
Mitre Dourado | 3 | 90 | 18.43 |
Dieter Rautenbach | 4 | 946 | 138.87 |
Jayme Luiz Szwarcfiter | 5 | 618 | 95.79 |