The Interval Graph Completion Problem for the Complete Multipartite Graphs  

作　　者：ZHANG Zhen-kun HOU Ya-lin 

机构地区：[1]Department of Mathematics, Huanghuai University, Zhumadian 463000, China

出　　处：《Chinese Quarterly Journal of Mathematics》2009年第2期290-297,共8页数学季刊（英文版）

基　　金：Supported by the Natural Science Foundation of Henan Province（082300460190）; Sponsored by Program for Science and Technology Innovation Talents in Universities of Henan Province.

摘　　要：The interval graph completion problem of a graph G includes two class problems： the profile problem and the pathwidth problem, denoted as P（G） and PW（G） respectively, where the profile problem is to find an interval supergraph with the smallest possible number of edges; the pathwidth problem is to find an interval supergraph with the smallest possible cliquesize. These two class problems have important applications to numerical algebra, VLSI- layout and algorithm graph theory respectively; And they are known to be NP-complete for general graphs. Some classes of special graphs have been investigated in the literatures. In this paper the exact solutions of the profile and the pathwidth of the complete multipartite graph Kn1,n2,...nr （r≥ 2） are determined.

关 键 词：the interval graph PROFILE PATHWIDTH the complete multipartite graph 

分 类 号：O157.5[理学—数学] TN47[理学—基础数学]