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.

Zitieren

Zitierform:

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

Zugriffsstatistik

Gesamt:
Volltextzugriffe:
Metadatenansicht:
12 Monate:
Volltextzugriffe:
Metadatenansicht:

Grafik öffnen

Rechte

Nutzung und Vervielfältigung:
Alle Rechte vorbehalten

Export