树的H_k-cordial性(英文)

如果可以给图G的边用集合{±1,±2,…,±k}中的元素标号,使得对G每个顶点v,其标号,即所有与其相邻的边的标号之和,都落在集合{±1,±2,…,±k}中,且|e(i)-e(-i)|≤1和|v(i)-v(-i)|≤1,其中v(i)和e(i)(1≤i≤k)分别是标号为i的顶点数和边数,那么就称该图G为Hk-cordial的.本文证明了除了K2以外,每棵树都是H3-cordial的.

一种联图的Cordial性

引入第一类图G的概念,即若存在一个标号f,使得|v0(G)-v1(G)|≤1,e0(G)≥e1(G),则称G为第一类图.证明了第一类图G与路P的联图G∨P,当P的阶数大于等于G的最大度的2倍加2,即|P|≥2Δ(G)+2时,都是Cordial图,并进一步给出图G是第一类图的两个充分条件.

关于图的运算与图的Pfaffian性(英文)

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

D(0,3)图的Cordial性

设dG(x)为图G中顶点x的度,若对于任意x∈V(G),dG(x)∈{i1,…,ik},k∈N,则称图G为D(i1,…,ik)图.研究D(0,3)图的Cordial性,利用分类讨论,调整标号的方法,证明了有最大度ΔG=Δ的图G,存在标号f,使得|v0(G)-v1(G)|≤1,|e0(G)-e1(G)|≤2Δ;在4个引理的基础上,证明了所有的D(0,3)图都是Cordial图.

一类brace中的thin边

证明若一个brace含有一个四圈C_(4),且该四圈中包含两个相邻的三度点,则该brace至少有一条thin边在该C_(4)中.