1 基本概念及背景介绍

本文研究的图都是无环、无重边的简单图.令G=(V, E)是n阶的图, 顶点集为V(G)={v₁, v₂, …, v_n}, 边集为E=E(G).G的邻接矩阵A(G)=(a_ij), 当且仅当v_i和v_j之间有边连, a_ij=1;否则, a_ij=0.邻接矩阵的正特征值个数、负特征值个数、零特征值个数分别称为图的正惯性指数、负惯性指数、零度, 分别记为p(G), n(G)和η(G).正、负惯性指数之差称为图的符号差, 记为s(G).正、负惯性指数之和称为图的秩, 记为r(G).n阶的完全图、路、圈、星图分别记为K_n, P_n, C_n, K_{1, n-1}.N(v)表示v点的邻点集合, d(v)表示v点的度.若图G满足|E(G)|=|V(G)|+k-1, 其中, |E(G)|是图G的边数, |V(G)|是图G的点数, 则图G称为k圈图.由k个仅相交于一个点的圈构成的图(图 1)称为α-图, 连接起点和终点的k条内点不交的路构成的图(图 2)称为θ-图.φ₁={所有恰含一个α-图作为导出子图的k圈图}和φ₂={所有恰含一个θ-图作为导出子图的k圈图}是两类k圈图.对于给定的H∈φ₁∪φ₂, H所含的导出子图a-图或θ-图称为图H的核, 记为χ_H.对于每一个点v∈χ_H, 将包含顶点v且不包含χ_H上其他点的H的最大连通导出子图记为H{v}, 易知H{v}是一棵树.

因为, 分子的稳定性和分子图的零度有关, 所以, 吸引了一大批学者对图的零度进行研究.而图的正、负惯性指数和图的零度密切相关, 关于图的正、负惯性指数的研究也引起了学者们的重视.文献[1]提出了一个关于符号差的猜想:

(1)

式中, c₃(G)和c₅(G)分别表示G中长为4k+3和4k+5 (k为非负整数)的圈的数目.

2012年, 文献[1]证明了任意简单图的符号差满足s(G)≤c₁(G), 其中, c₁(G)表示G中的奇圈数, 并证明了树、单圈图和双圈图对于式(1)成立.2014年, 文献[2]证明了简单图的线图对于式(1)成立.2014年, 文献[3]证明了边不交圈的图的符号差满足猜想.2015年, 文献[4]构造了一些满足式(1)的k圈图.2016年, 文献[5]研究了符号差等于奇圈数的图所满足的条件.本文证明了n阶图G中若存在点v, 满足d(v) < n-1且r(G)≠r(G-v)+1, 则式(1)对于图G成立, 并以实例说明了满足条件的图类的存在性.并证明了若H是k圈图, 如果存在点v∈χ_H是H{v}的可匹配点, 则H满足式(1).

2 主要引理

令A, B是n阶的实对称矩阵, 若存在n阶的可逆矩阵P, 使得P^TAP=B, 则称A和B合同, 记为.

引理1  ^[1]若G是树、单圈图或双圈图, 则-c₃(G)≤s(G)≤c₅(G).

引理2  ^[6]令A, B是同阶的实对称矩阵, 且, 则p(A)=p(B), n(A)=n(B), η(A)=η(B), s(A)=s(B).

引理3  ^[1]设G₁, G₂, …, G_t为G的所有连通分支, 则p(G)=p(G_i), n(G)=n(G_i), η(G)=η(G_i).

引理4  (特征值交错定理)^[7]若A是实对称矩阵, B是A的主子矩阵, 则B的特征值交错于A的特征值.特别地, 若n阶的图G有特征值λ₁≥λ₂≥…≥λ_n, 且H是G的一个删点子图, 有特征值μ₁≥μ₂≥…≥μ_n-1, 则λ_i≥μ_i≥λ_i+1, 1≤i≤n-1.

引理5  设v是图G中的一点, 则

证明  设n阶的图G有特征值λ₁≥λ₂≥…≥λ_r≥…≥λ_s-1≥λ_s≥λ_s+1≥…≥λ_s+r≥λ_s+r+1≥…≥λ_n.设H=G-v, H有特征值μ₁≥μ₂≥…≥μ_r≥…≥μ_s-1≥μ_s≥μ_s+1≥…≥μ_s+r≥μ_s+r+1≥…≥μ_n-1.由特征值交错定理可知, λ₁≥μ₁≥λ₂≥μ₂≥…≥λ_r≥μ_r≥…≥λ_s-1≥μ_s-1≥λ_s≥μ_s≥λ_s+1≥μ_s+1≥…≥λ_s+r≥μ_s+r≥λ_s+r+1≥μ_s+r+1≥…≥μ_n-1≥λ_n, 设λ_s为λ_i(1≤i≤n)里面最后一个正数.

a. 若μ_s>0, 则p(G)=p(H); 若μ_s+r=0, 则n(G)-1=n(H); 若μ_s+r < 0, 则n(G)=n(H).

b. 若μ_s < 0, 则p(G)-1=p(H), n(G)=n(H).

c. 若μ_s=0, 则p(G)-1=p(H); 若μ_s+r=0, 则n(G)-1=n(H); 若μ_s+r < 0, 则n(G)=n(H).

则对应的r(G)和s(G)可以表示为:

a. r(G)-1=r(H)或r(G)=r(H); s(G)+1=s(H)或s(G)=s(H).

b. r(G)-1=r(H); s(G)-1=s(H).

c. r(G)-2=r(H)或r(G)-1=r(H); s(G)=s(H)或s(G)-1=s(H).

综上所述, r(G)-2≤r(G-v)≤r(G), |s(G)-s(G-v)|≤1.

引理6^[2]  设v是图G的一个点, 若r(G-v)=r(G)或r(G-v)=r(G)-2, 则s(G)=s(G-v).

图G的一个匹配是指G的一个独立边集, 图G含边最多的一个匹配称为G的一个最大匹配.设G是一个图, v∈V(G).若存在G的一个最大匹配覆盖点v, 则称点v是G的一个可匹配点; 否则, 称点v是G的一个不可匹配点.若图G仅由一个点组成, 约定这个点是G的不可匹配点.

设图G₁和图G₂顶点不相交, u∈V(G₁), 在G₁∪G₂中将点u和G₂的任意k个点连接得到的图称为G₁和G₂的关于点u的一个k-连图, 记为G₁(u)⊙^kG₂.注意, 当k小于G₂的阶数时, 图G₁(u)⊙^kG₂并不唯一.

引理7  ^[1]设G是n阶图, u是树T的一个可匹配点, 则对每一正整数k(1≤k≤n), 有

a. p(T(u)⊙^kG)=p(T)+p(G);

b. n(T(u)⊙^kG)=n(T)+n(G);

c. η(T(u)⊙^kG)=η(T)+η(G).

3 主要结论

引理8  -c₃(K_n)≤s(K_n)≤c₅(K_n)成立.

证明  当n≤2时, 结论显然成立.以下假设n≥3, 由p(K_n)=1, n(K_n)=n-1, 故s(K_n)=p(K_n)-n(K_n)=2-n≤0≤c₅(K_n).当m>n时, 约定, 则由定义可知,

其中, 4k+3是小于n的最大整数, 且k为整数.显然,

综上所述, -c₃(K_n)≤s(K_n)≤c₅(K_n)成立.

引理9  设e是K_n中的任意一条边, 则-c₃(K_n-e)≤s(K_n-e)≤c₅(K_n-e)成立.

证明  当n≤3时, 结论显然成立.以下假设n≥4, 设K_n-e的邻接矩阵为A, 排列一下K_n-e中点的位置, 则邻接矩阵A可写为

经计算, |λE-A|=λ[λ²-(n-3)λ-2(n-2)](λ+1)^n-3.故p(K_n-e)=1, n(K_n-e)=n-2, η(K_n-e)=1, 从而, s(K_n-e)=p(K_n-e)-n(K_n-e)=3-n < 0≤c₅(K_n-e).以n₃(K_n-e)表示K_n-e中3-圈的个数, 则

故-c₃(K_n-e)≤2-n, 从而s(K_n-e)≥-c₃(K_n-e).

综上所述, -c₃(K_n-e)≤s(K_n-e)≤c₅(K_n-e)成立.

定理1  若n阶图G中存在点v, 满足d(v) < n-1且r(G)≠r(G-v)+1, 则-c₃(G)≤s(G)≤c₅(G).

证明  设G是由K_n删k条边得到的n阶图.若k=0或k=1, 由引理8和引理9可知结论成立.下面假设k≥2.

由于图G中存在点v满足d(v) < n-1, 所以, G-v可以看作由K_n-1删b条边后得到的图, 且b < k, 由归纳法可知, -c₃(G-v)≤s(G-v)≤c₅(G-v).因为, r(G)≠r(G-v)+1, 由引理5可知, r(G)=r(G-v)或者r(G)=r(G-v)+2, 从而由引理6可知, s(G)=s(G-v).由于c₃(G)≥c₃(G-v), c₅(G)≥c₅(G-v), 故-c₃(G)≤s(G)≤c₅(G).

推论1  若G中存在孤立点, 则-c₃(G)≤s(G)≤c₅(G).

证明  设H=G-v, 则

故r(G)=r(G-v), 由定理1可知, -c₃(G)≤s(G)≤c₅(G).

定理2  设H是k圈图, 若存在点v∈χ_H是H{v}的可匹配点, 则H满足-c₃(H)≤s(H)≤c₅(H).

证明  对于k=0(树), k=1(单圈图), 结论成立.下面假设k≥2.

因为, 存在点v∈χ_H是H{v}的可匹配点, 且H是H{v}⊙²(H-H{v})中的一个图, 则由引理7可知, p(H)=p(H{v})+p(H-H{v}), n(H)=n(H{v})+n(H-H{v}), 故p(H)-n(H)=[p(H{v})-n(H{v})]+[p(H-H{v})-n(H-H{v})], 即s(H)=s(H{v})+s(H-H{v}).由于v∈χ_H, 则v属于某个圈, 删去H{v}至少会破坏一个圈, 故H-H{v}的每一个连通分支都满足圈数小于k.假设H-H{v}的所有连通分支为H₁, H₂, …, H_m, 由归纳法可知, -c₃(H_i)≤s(H_i)≤c₅(H_i)(i=1, …, m), 从而有

由引理3可知,

由c₃(H), c₅(H)的定义可知, -c₃(H-H{v})≤s(H-H{v})≤c₅(H-H{v}).由于H{v}是树, 则s(H{v})=0, 从而s(H)=s(H-H{v}).而删点子图中的圈数不会超过原图中的圈数, 则-c₃(H)≤s(H)≤c₅(H).

4 满足r(G)≠r(G-v)+1的特殊图

推论2  设G是n (n≥2)阶的图, 若G中存在不相邻的两点u, v, 满足N(u)=N(v), 则-c₃(G)≤s(G)≤c₅(G).

证明  由于uv∉ E(G)且N(u)=N(v), 所以, A(G)中u, v对应的两行完全相同, 故r(G)=r(G-v)成立, 由定理1可知, -c₃(G)≤s(G)≤c₅(G).

推论3  设n阶的图G中存在点u, 若G中存在不同于u的k (k≥2)个点v₁, v₂, …, v_k, 满足N(v_i)⊆N(u)(i=1, …, k), 且N(u)=N(v₁)N(v₂)…N(v_k), 则-c₃(G)≤s(G)≤c₅(G).

证明  因为, N(u)是N(v₁), N(v₂), …, N(v_k)的不交并, 所以, 在G的邻接矩阵中可以通过v₁, v₂, …, v_k对应的行将u对应的行变为全零行.故r(G)=r(G-u)成立, 且u和v₁, v₂, …, v_k不相连, 因此, d(u) < n-1, 则由定理1可知结论成立.

推论4  设G是n (n≥3)阶的图, 若G中存在悬挂点, 则-c₃(G)≤s(G)≤c₅(G).

证明   G的邻接矩阵可写为

其中, 1对应的是悬挂点v, 则r(G)=r(G-v)+2, 且d(v) < n-1, 由定理1可知, -c₃(G)≤s(G)≤c₅(G).