数学季刊 ›› 2015, Vol. 30 ›› Issue (2): 308-316.doi: 10.13371/j.cnki.chin.q.j.m.2015.02.019
• • 上一篇
摘要: The interval graph completion problem on a graph G is to find an added edge set F such that G + F is an interval supergraph with the smallest possible number of edges. The problem has important applications to numerical algebra, V LSI-layout and algorithm graph theory etc; And it has been known to be N P-complete on general graphs. Some classes of special graphs have been investigated in the literatures. In this paper the interval graph completion problem on split graphs is investigated.
中图分类号: