|
Buletinul Academiei de Ştiinţe a Republicii Moldova. Matematica, 2016, Number 3, Pages 72–81
(Mi basm433)
|
|
|
|
This article is cited in 4 scientific papers (total 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.
Received: 27.07.2016
Citation:
Radu Buzatu, Sergiu Cataranciuc, “Nontrivial convex covers of trees”, Bul. Acad. Ştiinţe Repub. Mold. Mat., 2016, no. 3, 72–81
Linking options:
https://www.mathnet.ru/eng/basm433 https://www.mathnet.ru/eng/basm/y2016/i3/p72
|
Statistics & downloads: |
Abstract page: | 246 | Full-text PDF : | 74 | References: | 41 |
|