摘要
Let CCM denote the class of closed graphs with Cohen-Macaulay binomial edge ideals and PIG denote the class of proper interval graphs.Then CCM⊆PIG The PIG-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 CCM-completion problem.We give a method to construct all possible CCM-completions of a graph.We find the CCM-completion number and the set of all minimal CCM-completions for a large class of graphs.Moreover,for this class,we give a polynomial-time algorithm to compute the CCM-completion number and a minimum CCM-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.
