On the convexity number of graphs

Dourado, Mitre C.; Protti, Fábio; Rautenbach, Dieter GND; Szwarcfiter, Jayme Luiz

A set of vertices S in a graph is convex if it contains all vertices which belong to shortest paths between vertices in S. The convexity number c(G) of a graph G is the maximum cardinality of a convex set of vertices which does not contain all vertices of G. We prove NP-completeness of the problem to decide for a given bipartite graph G and an integer k whether c(G)\geq k. Furthermore, we identify natural necessary extension properties of graphs of small convexity number and study the interplay between these properties and upper bounds on the convexity number.

Cite

Citation style:

Dourado, Mitre C. / Protti, Fábio / Rautenbach, Dieter / et al: On the convexity number of graphs. 2009.

Access Statistic

Total:
Downloads:
Abtractviews:
Last 12 Month:
Downloads:
Abtractviews:

open graphic

Rights

Use and reproduction:
All rights reserved

Export