关于图的领域复盖  

作　　者：吴举林[1] 

机构地区：[1]青岛大学

出　　处：《青岛大学学报（自然科学版）》1990年第1期1-6,共6页Journal of Qingdao University(Natural Science Edition)

摘　　要：图G＝（V，E）中一个点V的领域是点V及其邻点导出的G的子图。领域复盖问题就是求一级量小个的领域，使其复盖子G的每一条边。本文证明了无三角形图上和分离图上的领域复盖问题是NP－完全问题。通过研究集族的强Helly性质，得到了领域复盖问题可转化为团复盖问题的条件一图的领域二分具有强Helly性质。文中给出了弦图的领域二分图具有强Helly性质的禁用子图形式的充分必要条件。

关 键 词：图 邻域复盖 NP-完全问题 弦图 邻域二分图 

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