图的局部匹配能量

《Discrete Applied Mathematics》：Local matching energy of a graph

　　

**摘要**

图的匹配能定义为其匹配多项式零的绝对值之和。受顶点局部能概念的启发，我们引入了局部匹配能的概念，其定义为当从图中删除一个顶点时匹配能的变化量。利用匹配多项式的生成函数之比，我们得到了局部匹配能的积分表示，并推导了该量的锐利界。特别地，我们证明了一个顶点的局部匹配能是非负的，且不超过其度数的平方根的两倍。我们还建立了连通图的更强界，并刻画了极值情形。

由于匹配能在森林中与经典图能重合，我们的结果也为树中顶点的局部能给出了极值。

**引言**

图的能由Gutman [1] 在化学分子轨道理论的背景下引入。设G为具有n个顶点的简单图，其邻接矩阵为A(G)，A(G)的特征值为λ?, λ?, …, λ?。则G的能定义为E(G) = Σ???? |λ?|。

该谱不变量在谱图论和数学化学中已被广泛研究；例如，参见Li、Shi和Gutman的专著 [2]。

最近，Espinal和Rada [3] 引入了顶点局部能的概念。设u ∈ V(G)，u在G中的局部能定义为E_G(u) = E(G) ? E(G?u)，其中G?u表示从G中删除顶点u及其所有关联边所得的图。量E_G(u)衡量了顶点u对图总能量的贡献。近年来，顶点局部能的若干结构性和极值方面已被研究；例如参见 [3]、[4]、[5]、[6]、[7]。

与图结构相关的另一个重要不变量是匹配能，由Gutman和Wagner [8] 引入。该量定义为图的匹配多项式零的绝对值之和。回顾一下，在无环图的情况下，图能（公式(1)）与匹配能（公式(2)）重合。

匹配多项式本身已被广泛研究；参见 [9]、[10]、[11]、[12]。其最显著的性质是它的所有零都是实数 [10]、[13]。近年来，匹配能已被广泛研究；例如参见 [14]、[15]、[16]、[17]、[18]。

受局部能概念以及匹配能在图论中所起作用的启发，我们引入了顶点局部匹配能的概念。该量衡量了当一个顶点被删除时图匹配能的变化。利用生成匹配多项式以及与顶点删除相关联的这些多项式之比，我们得到了局部匹配能的积分表示，并推导了该不变量的锐利界。

一个有趣的特例出现在树中。由于对于森林匹配能与经典图能重合，局部匹配能简化为顶点的通常局部能。特别地，若T是具有n≥2个顶点的树且u ∈ V(T)，则2(n?1?n?2) ≤ E_T(u) ≤ 2√(n?1)。上界仅当T ? K?,???且u是星的中心时取到，而下界仅当T ? K?,???且u是其中一个叶子时取到。

本文的组织如下。在第2节中，我们回顾匹配多项式和匹配能的基本概念，并引入顶点局部匹配能的概念。在第3节中，我们建立了任意图中该量的一般界。第4节包含了连通图的精化界以及极值情形的刻画。

**匹配能与局部匹配能**

我们首先回顾与图中匹配和匹配多项式相关的一些标准记号和基本概念。这些概念将用于引入顶点局部匹配能的概念。

设G为具有n个顶点的简单图。用m_k(G)表示G的k-匹配数，即选择k条独立边的数目。特别地，m?(G) = m是G的边数，且当k > ?n/2?时m_k(G) = 0。为了方便和一致性，定义m?(G) = 1。

**一般图中顶点的局部匹配能**

在本节中，我们建立了图中顶点局部匹配能的界。这些界类似于已知的顶点经典局部能的界。更精确地，我们证明如果u是图G的顶点，则局部匹配能ME_G(u)满足0 ≤ ME_G(u) ≤ 2√(d_G(u))，其中d_G(u)表示u在G中的度数。我们还刻画了在每个界中等式成立的图。

在本节中，我们考虑任意图。连通图的局部匹配能将在下一节讨论。

**连通图中顶点的局部匹配能**

在本节中，我们将前一节的结果专门应用于连通图，并推导局部匹配能的其他结构性质。连通性假设使我们能够获得生成匹配多项式之商的更强界。

**定理9** 设G为具有n≥2个顶点的连通图且u ∈ V(G)。则对每个x ≥ 0，
$$\frac{1+(n-1)x^2}{1+(n-2)x^2} \leq \frac{M_G(x)}{M_{G-u}(x)} \leq 1+(n-1)x^2$$
此外，
(a) M_G(x)/M_{G-u}(x) = 1+(n?1)x2对所有x ≥ 0成立当且仅当G ? K?,???且u是中心；
(b) M_G(x)/M_{G-u}(x) = 1…

**结论**

在本文中，我们引入了顶点局部匹配能的概念，定义为当删除一个顶点时图匹配能的变化量。以G和G?u的生成匹配多项式表示，我们得到了该量的积分表示。利用生成匹配多项式之比，我们推导了任意图中顶点局部匹配能的锐利界。特别地，如果u是图G的顶点，则0 ≤ ME_G(u) ≤ 2√(d_G(u))，其中d_G(u)…

Juan Rada | Ivan Gutman