Let Formula: see text denote the class of closed graphs with Cohen-Macaulay binomial edge ideals and Formula: see text denote the class of proper interval graphs. Then Formula: see text The Formula: see text-completion problem is a classical problem in graph theory as well as in molecular biology, and this problem is known to be NP-hard. In this paper, we study the Formula: see text-completion problem. We give a method to construct all possible Formula: see text-completions of a graph. We find the Formula: see text-completion number and the set of all minimal Formula: see text-completions for a large class of graphs. Moreover, for this class, we give a polynomial-time algorithm to compute the Formula: see text-completion number and a minimum Formula: see text-completion of a given graph. The unmixedness and Cohen-Macaulay properties of binomial edge ideals of induced subgraphs are investigated. Also, we discuss the accessible graph completion and the Cohen-Macaulay property of binomial edge ideals of whisker graphs.
Saha et al. (Thu,) studied this question.