On Nontrivial Covers and Partitions of Graphs by Convex Sets

Computer Science Journal of Moldova. 2018;26(1(76)):3-14

 

Journal Homepage

Journal Title: Computer Science Journal of Moldova

ISSN: 1561-4042 (Print)

Publisher: Institute of Mathematics and Computer Science of the Academy of Sciences of Moldova

Society/Institution: Institute of Mathematics and Computer Science of the Academy of Sciences of Moldova

LCC Subject Category: Science: Mathematics: Instruments and machines: Electronic computers. Computer science

Country of publisher: Moldova, Republic of

Language of fulltext: English

Full-text formats available: PDF

 

AUTHORS


Radu Buzatu (State University of Moldova, 60 A. Mateevici, MD-2009, Chisinau, Republic of Moldova)

Sergiu Cataranciuc (State University of Moldova, 60 A. Mateevici, MD-2009, Chisinau, Republic of Moldova)

EDITORIAL INFORMATION

Peer review

Editorial Board

Instructions for authors

Time From Submission to Publication: 16 weeks

 

Abstract | Full Text

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.