|
|||||
|
|
On the Convexity Number of Graphs |
|
| Authors: | Mitre C. Dourado Fábio Protti Dieter Rautenbach Jayme L. Szwarcfiter |
| Affiliation: | 1.Instituto de Matemática, Universidade Federal do Rio de Janeiro,Rio de Janeiro,Brazil;2.Instituto de Computa??o, Universidade Federal Fluminense,Niterói,Brazil;3.Institut für Optimierung und Operations Research, Universit?t Ulm,Ulm,Germany;4.Instituto de Matemática, NCE and COPPE, Universidade Federal do Rio de Janeiro,Rio de Janeiro,Brazil |
| Abstract: | 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) ≥ 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. |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ | |