一类乘积图的Pfaffian性

• 作者: 卢成晓 赵健
• 来源期刊: 南宁师范大学学报（自然科学版）
• 关键词: 图的定向 完美匹配 Pfaffian图
• 年，卷（期）: 2014,（4）
• 页码范围: 21-23
• 页数: 3页
• 分类号: O1576
• 语种: 中文

摘要

给图G的边任意一个定向，如果该有向图对应的斜邻接矩阵的行列式等于图 G 的完美匹配数的平方，那么就称这个定向是Pfaffian定向，图G称为Pfaffian图。研究Pfaffian图的意义在于它的完美匹配数能在多项式时间内得到。该文通过证明给出的定向是Pfaffian定向的方法证明了一类偶剖分图与三个顶点的路的乘积图是Pfaffian图。