Nontrivial convex covers of trees

Radu Buzatu ; Sergiu Cataranciuc

Buletinul Academiei de Ştiinţe a Republicii Moldova. Matematica, no. 3 (2016), pp. 72-81

Résumé

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 n3\rfloor$.