RUS  ENG
Full version
JOURNALS // Buletinul Academiei de Ştiinţe a Republicii Moldova. Matematica // Archive

Bul. Acad. Ştiinţe Repub. Mold. Mat., 2016 Number 3, Pages 72–81 (Mi basm433)

This article is cited in 4 papers

Research articles

Nontrivial convex covers of trees

Radu Buzatu, Sergiu Cataranciuc

Moldova State University, 60 A. Mateevici, MD-2009, Chişinău, Republic of Moldova

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

Keywords and phrases: convexity, convex cover, convex partition, tree, graph.

MSC: 05A18, 05C05, 05C85, 68Q25

Received: 27.07.2016

Language: English



© Steklov Math. Inst. of RAS, 2024