RO  EN
IMI/Publicaţii/CSJM/Ediţii/CSJM v.23, n.3 (69), 2015/

Convex graph covers

Authors: Radu Buzatu, Sergiu Cataranciuc
Keywords: Convexity, graphs, convex covers, convex partitions

Abstract

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.

State University of Moldova
60 A. Mateevici, MD-2009, Cișinău, Republic of Moldova
E-mail: ,

Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License

Fulltext

Adobe PDF document0.35 Mb