匹配覆盖图的阈函数(英文)

作者：郇潇; 鲁红亮; 于青林

来源：工程数学学报, 2014, 31(04): 622-632.

• 匹配覆盖
• 砖
• 双因子临界性
• 阈
• 负相关

一个图G是匹配覆盖的(或1-可扩的)如果它是连通的且G的每条边都被包含在一个完美匹配里.我们称一个图G为双因子临界的,如果对于G中的任意两个不同顶点x,y,Gx-y都有一个完美匹配.一个双因子临界图被称为砖块,如果它是3-连通的.本文对于双因子临界图与匹配覆盖二部图确定了它们的阈函数.对于非二部的匹配覆盖图,我们发现了一个概率序列,其表现就像一个阈.此外,我们证明几乎所有的3-连通图均是砖块.

• 单位
  西安交通大学; 苏州工业园区服务外包职业学院