Minimum convex cover of special nonoriented graphs
Închide
Conţinutul numărului revistei
Articolul precedent
Articolul urmator
225 9
Ultima descărcare din IBN:
2019-07-01 11:10
Căutarea după subiecte
similare conform CZU
519.83 (8)
Cercetări operaționale (OR) teorii şi metode matematice (94)
SM ISO690:2012
BUZATU, Radu. Minimum convex cover of special nonoriented graphs. In: Studia Universitatis (Seria Ştiinţe Exacte şi Economice). 2016, nr. 2(92), pp. 46-54. ISSN 1857-2073.
EXPORT metadate:
Google Scholar
Crossref
CERIF
BibTeX
DataCite
Dublin Core
Studia Universitatis (Seria Ştiinţe Exacte şi Economice)
Numărul 2(92) / 2016 / ISSN 1857-2073 /ISSNe 2345-1033

Minimum convex cover of special nonoriented graphs

CZU: 519.83
Pag. 46-54

Buzatu Radu
 
State University of Moldova
 
Disponibil în IBN: 11 octombrie 2016


Rezumat

A 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 covered 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.

ACOPERIREA CONVEXĂ MINIMĂ A GRAFURILOR SPECIALE NEORIENTATE Mulţimea de vârfuri S ale grafului G se numeşte convexă dacă pentru orice două vârfuri x, y din S toate vârfurile ce aparţin tuturor lanţurilor de lungime minimă cu extremităţile x, y se conţin în S. Se spune că G conţine o p-acoperire convexă dacă X(G) poate fi acoperită cu p mulţimi convexe. Numărul acoperirii convexe al lui G este cel mai mic număr p 2, pentru care G conţine o p-acoperire convexă. În particular, numărul acoperirii convexe netriviale al lui G este cel mai mic număr p 2, pentru care G conţine o p-acoperire convexă, în care orice mulţime constă din cel puţin 3 vârfuri. În această lucrare noi determinăm numărul acoperirii convexe şi numărul acoperirii convexe netriviale al unor clase speciale de grafuri obţinute din următoarele operaţii pe grafuri: suma, produsul cartezian, produsul lexicografic, coroana.

Cuvinte-cheie
nonoriented graphs, convex covers, convex number, cartesian product, lexicographic product, corona,

operations, join