|
Buletinul Academiei de Ştiinţe a Republicii Moldova. Matematica, 2016, номер 3, страницы 72–81
(Mi basm433)
|
|
|
|
Эта публикация цитируется в 4 научных статьях (всего в 4 статьях)
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
Аннотация:
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$.
Ключевые слова и фразы:
convexity, convex cover, convex partition, tree, graph.
Поступила в редакцию: 27.07.2016
Образец цитирования:
Radu Buzatu, Sergiu Cataranciuc, “Nontrivial convex covers of trees”, Bul. Acad. Ştiinţe Repub. Mold. Mat., 2016, no. 3, 72–81
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/basm433 https://www.mathnet.ru/rus/basm/y2016/i3/p72
|
|