2. Articole
Permanent URI for this collectionhttps://msuir.usm.md/handle/123456789/17
Browse
9 results
Search Results
Item MAXIMUM NONTRIVIAL CONVEX COVER NUMBER OF JOIN AND CORONA OF GRAPHS(2021) Buzatu, RaduLet G be a connected graph. We say that a set S ⊆ X(G) is convex in G if, for any two vertices x, y ∈ S, all vertices of every shortest path between x and y are in S. If 3 ≤ |S| ≤ |X(G)| − 1, then S is a nontrivial set. The greatest p ≥ 2 for which there is a cover of G by p nontrivial and convex sets is the maximum nontrivial convex cover number of G. In this paper, we determine the maximum nontrivial convex cover number of join and corona of graphs.Item MAXIMUM NONTRIVIAL CONVEX COVER NUMBER OF JOIN AND CORONA OF GRAPHS(Institutul de Matematică şi Informatică al AŞM, 2021) Buzatu, RaduLet G be a connected graph. We say that a set S ⊆ X(G) is convex in G if, for any two vertices x, y ∈ S, all vertices of every shortest path between x and y are in S. If 3 ≤ |S| ≤ |X(G)| − 1, then S is a nontrivial set. The greatest p ≥ 2 for which there is a cover of G by p nontrivial and convex sets is the maximum nontrivial convex cover number of G. In this paper, we determine the maximum nontrivial convex cover number of join and corona of graphsItem ON THE COMPUTATIONAL COMPLEXITY OF OPTIMIZATION CONVEX COVERING PROBLEMS OF GRAPHS(Institutul de Matematică şi Informatică al AŞM, 2020) Buzatu, RaduIn this paper we present further studies of convex covers and convex partitions of graphs. Let G be a finite simple graph. A set of vertices S of G is convex if all vertices lying on a shortest path between any pair of vertices of S are in S . If 3 ≤ | S | ≤ | X | − 1, then S is a nontrivial set. We prove that determining the minimum number of convex sets and the minimum number of nontrivial convex sets, which cover or partition a graph, is in general NP-hard. We also prove that it is NP-hard to determine the maximum number of nontrivial convex sets, which cover or partition a graph.Item UN MODEL MATEMATIC PENTRU OPTIMIZAREA ORGANIZĂRII ADMINISTRATIV - TERITORIALE A REPUBLICII MOLDOVA(CEP USM, 2018) Buzatu, Radu; Rabei, Cristina; Roșcovan, MihaiÎn lucrare se propune un model matematic de programare liniară în numere întregi pentru optimizarea organizării administrativ-teritoriale a Republicii Moldova care poate servi ca un instrument obiectiv și flexibil pentru obținerea și evaluarea scenariilor potenţiale de consolidare administrativ-teritorială.Item ON NONTRIVIAL COVERS AND PARTITIONS OF GRAPHS BY CONVEX SETS(Institutul de Matematică şi Informatică al Academiei de Ştiinţe a Moldovei, 2018) Buzatu, Radu; Cataranciuc, SergiuIn this paper we prove that it is NP-complete to decide whet- her 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 re- cursive formula that establishes the maximum nontrivial convex cover number of a tree.Item MAXIMUM NONTRIVIAL CONVEX COVER OF A TREE(CEP USM, 2017) Buzatu, RaduThe nontrivial convex p-cover problem of a tree is studied.We propose the recursive formula that determines the maximum nontrivial convex cover number of a tree.Item COVERING UNDIRECTED GRAPHS BY CONVEX SETS(Valines SRL, 2014) Buzatu, RaduThis paper is focused on some aspects of undirected graphs covering, in particular convex sets problem (CCS) and partitioning undirected graph into convex sets problem (PCS). We prove theorems regarding existence of graphs with fxed number of convex sets which serve as solutions to CCS and PCS problems.Item MINIMUM CONVEX COVER OF SPECIAL NON ORIENTED GRAPHS(CEP USM, 2016) Buzatu, RaduA vertex set S of a graph G is convex if all vertices of every shortest path between two of its vertices are in S. We say that G has a convex p-cover if X (G)can be overed by p convex sets. The convex cover number of G Is the least p 2 for which G has a convex p-cover.In particular, the nontrivial convex cover number of G is the least p 2 for which G has a convex p-cover, where every set contains at least 3 elements. In this paper we determine convex cover number and nontrivial convex cover number of special graphs resulting from some operations. We examine graphs resulting from join of graphs, Cartesian product of graphs, lexicographic product of graphs and corona of graphs.Item CONVEX GRAPH COVERS(Academy of Sciences of Moldova, 2015) Buzatu, Radu; Cataranciuc, SergiuWe study some properties of minimum convex covers and minimum convex partitions of simple graphs. We establish existence of graphs with fixed number of minimum convex covers and minimum convex partitions. It is known that convex p-cover problem is NP-complete for p\geq3 [5]. We prove that this problem is NP-complete in the case p=2. Also, we study covers and partitions of graphs when respective sets are nontrivial convex.