On the Convexity Number of Graphs
On the Convexity Number of Graphs
复制标题
关于图的凸数
DOI：
10.1007/s00373-011-1049-7
复制
发表时间：
2012
影响因子：
0.7
通讯作者：
J. Szwarcfiter
中科院分区：
文献类型：
--
作者：
M. C. Dourado;Fábio Protti;D. Rautenbach;J. Szwarcfiter
一个图的顶点集S是凸的，如果它包含所有属于S中顶点间最短路的顶点。图G的凸数c（G）是指不包含G的所有顶点的凸顶点集的最大基数。本文证明了对给定的二部图G和整数k判定c（G）≥ k的问题是NP-完全的。此外，我们确定了小凸数图的自然必要扩张性质，并研究了这些性质与凸数上界之间的相互作用。
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.