RO  EN
IMCS/Publications/CSJM/Issues/CSJM v.26, n.1 (76), 2018/

On Nontrivial Covers and Partitions of Graphs by Convex Sets

Authors: R. Buzatu, S. Cataranciuc
Keywords: Convexity, complexity, nontrivial convex cover, nontrivial convex partition, tree.

Abstract

In this paper we prove that it is NP-complete to decide whether a graph can be partitioned into nontrivial convex sets. We show that it can be verified in polynomial time whether a graph can be covered by nontrivial convex sets. Also, we propose a recursive formula that establishes the maximum nontrivial convex cover number of a tree.

State University of Moldova
60 A. Mateevici, MD-2009, Chi¸ sinˇ au, Republic of Moldova
E-mail: ,

Fulltext

Adobe PDF document0.13 Mb