与边控制相关的两类图

作者：庄蔚; 郝国亮

来源：新疆大学学报(自然科学版), 2019, 36(01): 11-16+38.

DOI：10.13568/j.cnki.651094.2019.01.002

• 边控制集
• 边控制极小图
• 边控制临界图

在图G中,如果存在一个边集D,使得不在D中的每一条边都与D中的某条边关联,则称D为G的边控制集.在G的所有边控制集中,包含边数最少的称为最小边控制集,其包含的边数称为边控制数,记为γ′(G).在一个图中,我们研究了加边或去边对该图边控制数的影响.一个图称为边控制临界图(边控制极小图)如果任意增加(去除)一条边都会使边控制数下降.在本文中,我们研究了这两类图的性质,并分别刻画了3-边控制临界图和3-点控制极小图.

• 单位
  东华理工大学; 厦门理工学院; 数学学院