Enumeration of perfect matchings of a type of Cartesian products of graphs

Let G be a graph and let Pm(G) denote the number of perfect matchings of G.We denote the path with m vertices by P_m and the Cartesian product of graphs G and H by G×H. In this paper, as the continuance of our paper [W. Yan, F. Zhang, Enumeration of perfect matchings of graphs with reflective symmetry by Pfaffians, Adv. Appl. Math. 32 (2004) 175-188], we enumerate perfect matchings in a type of Cartesian products of graphs by the Pfaffian method, which was discovered by Kasteleyn. Here are some of our results:1. Let T be a tree and let C_n denote the cycle with n vertices. Then Pm(C₄×T)=∏(2+α²), where the product ranges over all eigenvalues α of T. Moreover, we prove that Pm(C₄×T) is always a square or double a square.2. Let T be a tree. Then Pm(P₄×T)=∏(1+3α²+α⁴), where the product ranges over all non-negative eigenvalues α of T.3. Let T be a tree with a perfect matching. Then Pm(P₃×T)=∏(2+α²), where the product ranges over all positive eigenvalues α of T. Moreover, we prove that Pm(C₄×T)=[Pm(P₃×T)]².     

[a,b]-对等图的范-型条件

既是[a,b]-覆盖又是[a,b]-消去的图称为[a,b]-对等图.设1≤aan+1a+b,则G为[a,b]-对等图.给出了一个图是[a,b]-对等图的关于范-型条件及邻域并的若干充分条件,并指出定理中的条件在一定意义上是最好可能的.     

Parameter testing in bounded degree graphs of subexponential growth

Parameter testing algorithms are using constant number of queries to estimate the value of a certain parameter of a very large finite graph. It is well‐known that graph parameters such as the independence ratio or the edit‐distance from 3‐colorability are not testable in bounded degree graphs. We prove, however, that these and several other interesting graph parameters are testable in bounded degree graphs of subexponential growth. © 2010 Wiley Periodicals, Inc. Random Struct. Alg., 2010     

Graphs having distance-n domination number half their order

For any positive integer n and any graph G a set D of vertices of G is a distance-n dominating set, if every vertex vV(G)−D has exactly distance n to at least one vertex in D. The distance-n domination number γ_=n(G) is the smallest number of vertices in any distance-n dominating set. If G is a graph of order p and each vertex in G has distance n to at least one vertex in G, then the distance-n domination number has the upper bound p/2 as Ore's upper bound on the classical domination number. In this paper, a characterization is given for graphs having distance-n domination number equal to half their order, when the diameter is greater or equal 2n−1. With this result we confirm a conjecture of Boland, Haynes, and Lawson.     

一类泛连通无爪图

本文证明了如果Ｇ是３连通无爪图，且Ｇ的每个导出子图Ａ，Ａ＋都满足（ａ１，ａ２），则Ｇ是泛连通图（除了当ｕ，ｖ∈Ｖ（Ｇ），ｄ（ｕ，ｖ）＝１时，Ｇ中可能不存在（ｕ，ｖ）－ｋ路外，这里２≤ｋ≤４）．     

基于改进的分块压缩感知红外图像重建

针对基于压缩感知理论的红外图像重建问题,提出一种基于改进的分块压缩感知红外图像重建方法。该方法首先对原始红外图像进行分块,并对每个子块用相同的观测矩阵进行随机观测,获得少量的观测数据;然后利用谱图小波变换优异的稀疏特性,将其引入平滑投影Landweber算法进行迭代优化重建,同时采用混合中值滤波进行处理以增加图像的平滑度和减少块伪影,最后输出满足要求的高质量红外图像。实验结果表明,在相同采样率下,该方法对于不同类型红外图像的重建性能均优于目前广为采用的一些小波压缩感知方法,可获得更高质量的红外图像。