Name
Abstract | ||
|---|---|---|
Given a graph G, a set S subset of V (G) is Delta-convex if there is no vertex u is an element of V (G) \ S forming a triangle with two vertices of S. The Delta-convex hull of S is the minimum Delta-convex set containing S. The Delta-hull number of a graph G is the cardinality of a minimum set such that its Delta-convex hull is V (G). We show that the problem of deciding whether the Delta-hull number of a general graph is at most k is an NP-complete problem and present polynomial-time algorithms for computing the Delta-hull number of some graph classes including chordal graphs, dually chordal graphs, and cographs. (C) 2020 Elsevier B.V. All rights reserved. |
Year | DOI | Venue |
|---|---|---|
2020 | 10.1016/j.tcs.2020.08.024 | THEORETICAL COMPUTER SCIENCE |
Keywords | DocType | Volume |
Chordal graph,Cograph,Dually chordal graph,Graph convexity,Hull number | Journal | 844 |
ISSN | Citations | PageRank |
0304-3975 | 0 | 0.34 |
References | Authors | |
0 | 5 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Bijo S. Anand | 1 | 11 | 2.69 |
| Arun Anil | 2 | 0 | 0.68 |
| Manoj Changat | 3 | 170 | 30.93 |
| Mitre Dourado | 4 | 90 | 18.43 |
| Sabeer Sain Ramla | 5 | 0 | 0.34 |