Institutul de Matematică şi Informatică "Vladimir Andrunachievici"
Universitatea de Stat din MoldovaRO EN
On Nontrivial Covers and Partitions of Graphs by Convex Sets
Authors: R. Buzatu, S. Cataranciuc
Keywords: Convexity, complexity, nontrivial convex cover, nontrivial convex partition, tree.
– 0.13 Mb
Keywords: Convexity, complexity, nontrivial convex cover, nontrivial convex partition, tree.
Abstract
In this paper we prove that it is NP-complete to decide whether a graph can be partitioned into nontrivial convex sets. We show that it can be verified in polynomial time whether a graph can be covered by nontrivial convex sets. Also, we propose a recursive formula that establishes the maximum nontrivial convex cover number of a tree.State University of Moldova
60 A. Mateevici, MD-2009, Chi¸ sinˇ au, Republic of Moldova
E-mail: ,
60 A. Mateevici, MD-2009, Chi¸ sinˇ au, Republic of Moldova
E-mail: ,
Fulltext
– 0.13 Mb
Contents
- On Nontrivial Covers and Partitions of Graphs by Convex Sets
- Bounds for the Independence Number in k-Step Hamiltonian Graphs
- Vertex weighted Laplacian Energy of union of graphs
- Parallel algorithm to find Bayes-Nash solution to the bimatrix informational extended game
- Implementation of the Composition-nominative Approach to Program Formalization in Mizar
- Finite automata over magmas: models and some applications in Cryptography
- Annotation on PhD Thesis
- About International Conference MITI2018
