On the hull number of some graph classes. (English) Zbl 1419.05049
Summary: 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\in 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\subseteq V\), let \(I[S]=\cup_{u,v\in S}I[u,v]\). A subset \(S\subseteq V\) is geodesically convex or convex if \(I[S]=S\). In other words, a subset \(S\) is convex if, for any \(u,v\in S\) and for any shortest \((u,v)\)-path \(P\), \(V(P)\subseteq S\). Given a subset \(S\subseteq 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 \(\operatorname{hn}(G)\). The hull number problem is to decide whether \(\operatorname{hn}(G)\leq k\), for a given graph \(G\) and an integer \(k\). M. C. Dourado et al. [Discrete Math. 309, No. 18, 5668–5674 (2009; Zbl 1215.05184)] showed that this problem is NP-complete in general graphs.
In this paper, we answer an open question of Dourado et al. [loc. cit.] 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 [J. Araujo et al., Electron. Notes Discrete Math. 38, 49–55 (2011; Zbl 1274.05120)] 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+\lceil\frac{3(n-1)}{5}\rceil\) in general, at most \(1+\lceil\frac{n-1}{2}\rceil\) if \(G\) is regular or has no triangle, and at most \(1+\lceil\frac{n-1}{3}\rceil\) if \(G\) has girth at least 6.
For any two vertices \(u,v\in 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\subseteq V\), let \(I[S]=\cup_{u,v\in S}I[u,v]\). A subset \(S\subseteq V\) is geodesically convex or convex if \(I[S]=S\). In other words, a subset \(S\) is convex if, for any \(u,v\in S\) and for any shortest \((u,v)\)-path \(P\), \(V(P)\subseteq S\). Given a subset \(S\subseteq 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 \(\operatorname{hn}(G)\). The hull number problem is to decide whether \(\operatorname{hn}(G)\leq k\), for a given graph \(G\) and an integer \(k\). M. C. Dourado et al. [Discrete Math. 309, No. 18, 5668–5674 (2009; Zbl 1215.05184)] showed that this problem is NP-complete in general graphs.
In this paper, we answer an open question of Dourado et al. [loc. cit.] 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 [J. Araujo et al., Electron. Notes Discrete Math. 38, 49–55 (2011; Zbl 1274.05120)] 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+\lceil\frac{3(n-1)}{5}\rceil\) in general, at most \(1+\lceil\frac{n-1}{2}\rceil\) if \(G\) is regular or has no triangle, and at most \(1+\lceil\frac{n-1}{3}\rceil\) if \(G\) has girth at least 6.
MSC:
| 05C10 | Planar graphs; geometric and topological aspects of graph theory |
| 05C12 | Distance in graphs |
| 05C38 | Paths and cycles |
| 68Q17 | Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) |
