Nontrivial convex covers of trees
Buletinul Academiei de Ştiinţe a Republicii Moldova. Matematica, no. 3 (2016), pp. 72-81
Voir la notice de l'article provenant de la source Math-Net.Ru
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$.
@article{BASM_2016_3_a5,
author = {Radu Buzatu and Sergiu Cataranciuc},
title = {Nontrivial convex covers of trees},
journal = {Buletinul Academiei de \c{S}tiin\c{t}e a Republicii Moldova. Matematica},
pages = {72--81},
publisher = {mathdoc},
number = {3},
year = {2016},
language = {en},
url = {http://geodesic.mathdoc.fr/item/BASM_2016_3_a5/}
}
Radu Buzatu; Sergiu Cataranciuc. Nontrivial convex covers of trees. Buletinul Academiei de Ştiinţe a Republicii Moldova. Matematica, no. 3 (2016), pp. 72-81. http://geodesic.mathdoc.fr/item/BASM_2016_3_a5/