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\ge 4$ vertices has a nontrivial convex $p$-cover for every $p$, $2\le p\le {\phi }_{cn}^{max}(G)$. Also, we prove that it can be decided in polynomial time whether a tree on $n\ge 6$ vertices has a nontrivial convex $p$-partition, for a fixed $p$, $2\le p\le \lfloor \frac{n}{3}\rfloor$.

Bibliographie

[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)