MINIMUM CONVEX COVER OF SPECIAL NONORIENTED GRAPHS

Radu BUZATU

Abstract


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  can be covered by p convex sets. The convex cover number of G is the least  for which G has a convex p-cover. In particular, the nontrivial convex cover number of G is the least  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.


Keywords


nonoriented graphs, convex covers, convex number, operations, join, cartesian product, lexicographic product, corona

Full Text:

PDF

References


BOLTEANSKY, V., SOLTAN, P. Combinatorial geometry of the various classes of convex sets. Chişinău, 1978, p.282 (in Russian).

ARTIGAS, D., DANTAS, S., DOURADO, M.C., SXWARCFITER, J.L. Convex covers of graphs. In: Matematica Contemporanea, Sociedade Brasileira de Matematica, 2010, vol.39, p.31-38.

BERGE, C. Theory of graphs and its applications. Methuen, London, 1962.

BUZATU, R., CATARANCIUC, S. Convex graph covers. In: Computer Science Journal of Moldova, 2015, vol.23, no3(69), p.251-269.

CATARANCIUC, S., SUR N. D-convex simple and quasi-simple graphs. Chişinău: Moldova State University, 2009, p.199 (in Romanian).

ARTIGAS, D., DANTAS, S., DOURADO, M.C., SXWARCFITER, J.L. Partitioning a graph into convex sets. In: Discrete Mathematics, 2011, vol.311, p.1968-1977.

BUZATU, R. Covers of graphs by two convex sets. In: Studia univ. Babeş-Bolyai, Series Informatica, vol.LXI, no1, 2016, p.5-22.

BUZATU, R., CATARANCIUC, S. Cover of undirected graph into nontrivial convex sets. In: Proceedings of the 5th International Conference: Mathematical Modeling, Optimization and Information Technology, March 22-25, Chişinău, Moldova, 2016, p.64-71 (in Romanian).

CANOY, S.R., GARCES, I.J.L. Convex sets under some graph operations. In: Graphs Combin., 2002, 18(4), p.787-793.

CANOY, S.R., LAJA, L. Convex Sets in the Corona and Conjunction of Graphs. In: Congressus numeratium, 2006, vol.180, p.207-216.

ANAND, B.S., CHANGAT, M., KLAVZAR, S., PETERIN, I. Convex sets in lexicographic products of graphs. In: Graphs Combin. 2012, 28, p.77-84.


Refbacks

  • There are currently no refbacks.