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算法进行迭代优化重建,同时采用混合中值滤波进行处理以增加图像的平滑度和减少块伪影,最后输出满足要求的高质量红外图像。实验结果表明,在相同采样率下,该方法对于不同类型红外图像的重建性能均优于目前广为采用的一些小波压缩感知方法,可获得更高质量的红外图像。     

庚酸甲酯高温燃烧化学动力学机理的系统简化和分析

采用详细化学反应动力学机理的系统简化方法, 对庚酸甲酯高温燃烧化学动力学机理进行了系统简化. 首先采用两步直接关系图法(Directed relation graph method, DRG)和主成分分析(Principle component analysis, PCA)方法对由1087个物种、4592步可逆反应组成的庚酸甲酯燃烧的详细机理进行框架简化, 得到了包含108个物种, 547步基元反应的框架机理. 在此框架机理基础上, 进一步采用计算奇异值摄动法(Computational singular perturbation, CSP)对框架机理进行时间尺度分析, 再选取30个准稳态物种, 采用准稳态近似(Quasi steady state approximation, QSSA)方法构建了包含78个物种、74步总包反应的全局简化机理. 模拟结果表明, 在较宽的参数范围内, 框架机理和全局简化机理均能重现庚酸甲酯高温燃烧时的点火延迟、物种浓度分布和熄火等燃烧特性. 此外, 基于框架机理阐明了庚酸甲酯高温燃烧的反应路径和对点火有重要影响的基元反应. 与详细机理相比, 框架机理保留了良好的精确性和全局性, 可以很好地反映庚酸甲酯的燃烧特性, 有助于对生物柴油的燃烧过程的理解.     

分子轨道图形理论中对称轴定理

本文试图以浅显明确的形式描述对称轴定理，使之能与对称面定理相媲美，并对对称轴定理作一定的扩展，给出分子轨道构造定理。