RUS  ENG
Полная версия
ЖУРНАЛЫ // Buletinul Academiei de Ştiinţe a Republicii Moldova. Matematica // Архив

Bul. Acad. Ştiinţe Repub. Mold. Mat., 2016, номер 3, страницы 72–81 (Mi basm433)

Эта публикация цитируется в 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.

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

Поступила в редакцию: 27.07.2016

Язык публикации: английский



© МИАН, 2024