Geodesic
Nontrivial convex covers of trees
Buletinul Academiei de Ştiinţe a Republicii Moldova. Matematica, no. 3 (2016), pp. 72-81 
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/
@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},
     year = {2016},
     number = {3},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/BASM_2016_3_a5/}
}
TY  - JOUR
AU  - Radu Buzatu
AU  - Sergiu Cataranciuc
TI  - Nontrivial convex covers of trees
JO  - Buletinul Academiei de Ştiinţe a Republicii Moldova. Matematica
PY  - 2016
SP  - 72
EP  - 81
IS  - 3
UR  - http://geodesic.mathdoc.fr/item/BASM_2016_3_a5/
LA  - en
ID  - BASM_2016_3_a5
ER  - 
%0 Journal Article
%A Radu Buzatu
%A Sergiu Cataranciuc
%T Nontrivial convex covers of trees
%J Buletinul Academiei de Ştiinţe a Republicii Moldova. Matematica
%D 2016
%P 72-81
%N 3
%U http://geodesic.mathdoc.fr/item/BASM_2016_3_a5/
%G en
%F BASM_2016_3_a5

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$.

[1] Boltyansky V., Soltan P., Combinatorial geometry of various classes of convex sets, Chişinǎu, 1978 (in Russian)

[2] Cataranciuc S., Sur N., D-convex simple and quasi-simple graphs, Chişinǎu, Republic of Moldova, 2009 (in Romanian) | MR

[3] Harary F., Graph Theory, Addison-Wesley, 1969 | MR | Zbl

[4] Artigas D., Dantas S., Dourado M. C., Szwarcfiter J. L., “Convex covers of graphs”, Matemática Contemporânea, Sociedade Brasileira de Matemática, 39 (2010), 31–38 | MR | Zbl

[5] Artigas D., Dantas S., Dourado M. C., Szwarcfiter J. L., “Partitioning a graph into convex sets”, Discrete Mathematics, 311 (2011), 1968–1977 | DOI | MR | Zbl

[6] Buzatu R., Cataranciuc S., “Convex graph covers”, Computer Science Journal of Moldova, 23:3(69) (2015), 251–269 | MR

[7] Buzatu R., “Covers of graphs by two convex sets”, Studia univ. Babeş-Bolyai, Series Informatica, 61:1 (2016), 5–22 | MR

[8] Buzatu R., Cataranciuc S., “Cover of undirected graph into nontrivial convex sets”, Proceedings of the 5th International Conference: Mathematical Modeling, Optimization and Information Technology (March 22–25, 2016, Chişinǎu, Republic of Moldova), 64–79 (in Romanian)