The Hull Number in the Convexity of Induced Paths of Order 3

摘要

A set S of vertices of a graph G is P_3* -convex if there is no vertex outside S having two non-adjacent neighbors in S. The P_3*-convex hull of S is the minimum P_3*-convex set containing S. If the P_3*-convex hull of S is V(G), then S is a P_3*-hull set. The minimum size of a P_3*-hulI set is the P_3*-hull number of G. In this paper, we show that the problem of deciding whether the P_3*-hull number of a chordal graph is at most k is NP-complete and present a linear-time algorithm to determine this parameter and provide a minimum P_3*-hull set for unit interval graphs.