关于图的运算与图的Pfaffian性

关于一般的图的完美匹配计数的问题已证实是NP-hard问题.但Pfaffian图的完美匹配计数问题(以及其它相关问题)却能够在多项式时间内解决.由此可见图的Pfaffian性的重要性.在这篇文章中,我们研究了若干种影响图的Pfaffian性的运算.     

树的Hk-cordial性

如果可以给图G的边用集合（±1,±2,.. ,±k）中的元素标号,使得对G每个顶点u,其标号,即所有与其相邻的边的标号之和,都落在集合（±1,±2,.. ,±k）中,且Ie（i）-e（-i）I≤1和lu（i）-u（-i）1≤1,其中t心）和e（i）（1≤i≤k）分别是标号为i的顶点数和边数,那么就称该图G为Hk-cordial的．本文证明了除了尥以外,每棵树都是H3-cordial的．