摘要
一个图的最小填充数就是确定顶点的一个标号顺序,按此顺序消去顶点时最少的添加边数。格子图是实际中遇到最多的一类稀疏图。利用图的分解定理和约化准则,讨论了平面格子图Pm×Pn的最小填充,确定了m=4,5,6时的填充数表达式和它的一些界。
The minimum fill-in of graphs is the minimum added edgs number when the vertices are eliminated by an Labeling of the vertices in graphs. This paper discusses the minimum fill,in of the Grid Graph Pm×Pn（m=4,5,6） using of the decomposed theorem and reductive rule, and formula of minimum fill-in are determined.
出处
《重庆科技学院学报（自然科学版）》
CAS
2009年第4期171-173,共3页
Journal of Chongqing University of Science and Technology：Natural Sciences Edition
基金
河南省自然科学基金项目(0511011400)
关键词
最小填充
标号
格子图
分解定理
minimum fill-in
labeling
grid graph
decomposed theorem
