On the hull number of some graph classes

作者：Araujo J^*; Campos V; Giroire F; Nisse N; Sampaio L; Soares R

来源：Theoretical Computer Science, 2013, 475: 1-12.

DOI：10.1016/j.tcs.2012.12.035

• Graph convexity
• Hull number
• Bipartite graph
• Cobipartite graph
• Cactus graph
• (q, q-4)-Graph

In this paper, we study the geodetic convexity of graphs, focusing on the problem of the complexity of computing a minimum hull set of a graph in several graph classes.
For any two vertices u, v is an element of V of a connected graph G = (V, E), the closed interval I[u, v] of u and v is the set of vertices that belong to some shortest (u, v)-path. For any S subset of V, let I[S] = boolean OR(u, v is an element of S) I[u, v]. A subset S subset of V is geodesically convex or convex if I[S] = S. In other words, a subset S is convex if, for any u, v is an element of S and for any shortest (u, v)-path P, V (P) C S. Given a subset S C V, the convex hull I-h [S] of S is the smallest convex set that contains S. We say that S is a hull set of G if I-h [S] = V. The size of a minimum hull set of G is the hull number of G, denoted by hn(G). The HULL NUMBER problem is to decide whether hn(G) <= k, for a given graph G and an integer k. Dourado et al. showed that this problem is NP-complete in general graphs.
In this paper, we answer an open question of Dourado et al. (2009) [1] by showing that the HULL NUMBER problem is NP-hard even when restricted to the class of bipartite graphs. Then, we design polynomial-time algorithms to solve the HULL NUMBER problem in several graph classes. First, we deal with the class of complements of bipartite graphs. Then, we generalize some results in Araujo et al. (2011) [2] to the class of (q, q 4)-graphs and to cacti. Finally, we prove tight upper bounds on the hull numbers. In particular, we show that the hull number of an n-node graph G without simplicial vertices is at most 1 + r3015-o 1 in general, at most 1 inverted right perpendicularn-1/2inverted left perpendicular is regular or has no triangle, and at most 1 + inverted left perpendicularn-1/3inverted right perpendicular if G has girth at least 6.

• 出版日期2013-3-4
• 单位INRIA