Convex graph covers
We study some properties of minimum convex covers and minimum convex partitions of simple graphs. We establish existence of graphs with fixed number of minimum convex covers and minimum convex partitions. It is known that convex $p$-cover problem is NP-complete for $p\geq3$ [5]. We prove that this p...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Vladimir Andrunachievici Institute of Mathematics and Computer Science
2015-11-01
|
| Series: | Computer Science Journal of Moldova |
| Subjects: | |
| Online Access: | http://www.math.md/files/csjm/v23-n3/v23-n3-(pp251-269).pdf |
| _version_ | 1828151175366574080 |
|---|---|
| author | Radu Buzatu Sergiu Cataranciuc |
| author_facet | Radu Buzatu Sergiu Cataranciuc |
| author_sort | Radu Buzatu |
| collection | DOAJ |
| description | We study some properties of minimum convex covers and minimum convex partitions of simple graphs. We establish existence of graphs with fixed number of minimum convex covers and minimum convex partitions. It is known that convex $p$-cover problem is NP-complete for $p\geq3$ [5]. We prove that this problem is NP-complete in the case $p=2$. Also, we study covers and partitions of graphs when respective sets are nontrivial convex. |
| first_indexed | 2024-04-11T21:54:00Z |
| format | Article |
| id | doaj.art-59c5dbbf2de943cf983d422a7cf34392 |
| institution | Directory Open Access Journal |
| issn | 1561-4042 |
| language | English |
| last_indexed | 2024-04-11T21:54:00Z |
| publishDate | 2015-11-01 |
| publisher | Vladimir Andrunachievici Institute of Mathematics and Computer Science |
| record_format | Article |
| series | Computer Science Journal of Moldova |
| spelling | doaj.art-59c5dbbf2de943cf983d422a7cf343922022-12-22T04:01:10ZengVladimir Andrunachievici Institute of Mathematics and Computer ScienceComputer Science Journal of Moldova1561-40422015-11-01233(69)251269Convex graph coversRadu Buzatu0Sergiu Cataranciuc1State University of Moldova, 60 A. Mateevici, MD-2009, Chisinau, Republic of MoldovaState University of Moldova, 60 A. Mateevici, MD-2009, Chisinau, Republic of MoldovaWe study some properties of minimum convex covers and minimum convex partitions of simple graphs. We establish existence of graphs with fixed number of minimum convex covers and minimum convex partitions. It is known that convex $p$-cover problem is NP-complete for $p\geq3$ [5]. We prove that this problem is NP-complete in the case $p=2$. Also, we study covers and partitions of graphs when respective sets are nontrivial convex.http://www.math.md/files/csjm/v23-n3/v23-n3-(pp251-269).pdfConvexitygraphsconvex coversconvex partitions |
| spellingShingle | Radu Buzatu Sergiu Cataranciuc Convex graph covers Computer Science Journal of Moldova Convexity graphs convex covers convex partitions |
| title | Convex graph covers |
| title_full | Convex graph covers |
| title_fullStr | Convex graph covers |
| title_full_unstemmed | Convex graph covers |
| title_short | Convex graph covers |
| title_sort | convex graph covers |
| topic | Convexity graphs convex covers convex partitions |
| url | http://www.math.md/files/csjm/v23-n3/v23-n3-(pp251-269).pdf |
| work_keys_str_mv | AT radubuzatu convexgraphcovers AT sergiucataranciuc convexgraphcovers |