RO  EN
IMCS/Publications/BASM/Issues/BASM n.3(82), 2016/

Nontrivial convex covers of trees

Authors: Radu Buzatu, Sergiu Cataranciuc

Abstract

We establish conditions for the existence of nontrivial convex covers and nontrivial convex partitions of trees. We prove that a tree $G$ on $n\ge4$ vertices has a nontrivial convex $p$-cover for every $p$, $2\le p\le\varphi_{cn}^{max}(G)$. Also, we prove that it can be decided in polynomial time whether a tree on $n\ge6$ vertices has a nontrivial convex $p$-partition, for a fixed $p$, $2\le p\le \lfloor\frac{n}{3}\rfloor$.

Moldova State University
60 A. Mateevici, MD-2009, Chisinau
Republic of Moldova
E-mail: ,

Fulltext

Adobe PDF document0.14 Mb