双圈图的无符号拉普拉斯特征多项式的系数

徐丽珍， 何常香

（上海理工大学 理学院，上海 200093）

1 基本定义

式中，I为n 阶单位矩阵.

如果连通图G 的边数等于顶点数，则称G 为单圈图；如果连通图G 的边数等于顶点数加1，则称G为双圈图.G－e表示由G 删去边e后得到的图.

定义1［1］设H 是图G 的一个生成子图，若H的连通分支是树，或者是圈长为奇数的单圈图，则称H 是图G 的一个TU－子图；若H 恰有c个圈长为奇数的单圈分支和s个树分支T1，T2，…，Ts，则定义表示树Ti的阶数.

引理1［1］设Hi为图G 中所有具有i 条边的TU－子图集合，则式（1）中p0（G）＝1，

在引理1中，由于Hi的确定比较困难，所以，pi（G）也很难被确定.文献［1］给出了无符号拉普拉斯特征多项式系数p1（G）和p2（G）的表达式.文献［2］给出了p3（G）的表达式.文献［3］给出了经删边、剖分及移邻等变换后所得图G′的pi（G′）的绝对值与原图pi（G）的绝对值的大小关系，并以此为工具，确定了无符号拉普拉斯特征多项式系数绝对值最小的单圈图.更多关于系数的研究见文献［4－9］.现主要研究双圈图的无符号拉普拉斯特征多项式的常数项.

2 双圈图的分类

设B（n）为所有n 阶双圈图的集合，不含悬挂点的双圈图有B（r，s，l）和B（Pk，Pl，Pt）这两类，如图1所示.

易见Bn（n）＝B1（n）∪B2（n）.

图1 B（r，s，l）和B（Pk，Pl，Pt）Fig.1 B（r，s，l）and B（Pk，Pl，Pt）

3 双圈图的无符号拉普拉斯系数pn（G）

现主要给出两类双圈图的无符号拉普拉斯特征多项式的常数项.

定义4 设图G 是n 阶连通图，e＝v1v2是图G的一条非悬挂边，在图G 中的点v1处添加一条悬挂边，再将边e收缩（即将点v1和v2粘合）后得到一个新的n阶连通图G′＝τ（G，1，2）.

定理1 设G∈B1（n），则

证明 由引理1可知

若H∈Hn，则H 为G 的边数为n＋1－1＝n 的TU－子图，即存在e∈E（G）使得H ＝G－e；若e∉E（），则G－e∉Hn.以下假设e∈E），按r，s的奇偶性进行讨论.

情形1 若r，s均为偶数.

此时Hn＝φ，从而有pn（G）＝0.

情形2 若r，s的奇偶性不同.

不失一般性，不妨设x＝r 为偶数（即Cr为偶圈）.只有当e∈E（Cr）时，H＝G－e才是G 的TU－子图，并且此时的W（H）＝4，从而有

情形3 若r，s均为奇数.

若e不在圈上，则G－e是G 的含2个奇单圈分支的TU－子图，故W（H）＝42；若e在圈上，则Ge是G 的恰有1个奇单圈分支的TU－子图，且W（H）＝4.综上

由定理1的结论可知，收缩加悬挂边后双圈图中圈的奇偶性发生改变，所以，图的无符号拉普拉斯特征多项式系数pn（G）的大小关系很难确定.

例1 设图G 的阶数为n＝9，图G′和G″是由图G 收缩边v1v2加一条悬挂边于点v1而得到的，如图2和3所示.

图2 图G1和图G′＝τ（G1，1，2）Fig.2 Graph G1and G′＝τ（G1，1，2）

图3 图G2和图G″＝τ（G2，1，2）Fig3 Graph G2and G″＝τ（G2，1，2）

显然pn（G1）＝pn（G2）＝－16，pn（G′）＝－（4×5＋4×3＋42×1）＝－48，pn（G″）＝0，pn（G1）≥pn（G′），pn（G2）≤pn（G″）.

定理2 设G∈B2（n），则

式中，x，y 为k，l，t中奇偶性相同的2个数.

证明 由引理1可知

若H∈Hn，则H 为G 的边数为n＋1－1＝n 的TU－子图，即存在e∈G 使得H ＝G－e；若e∉，则G－e∉Hn.以下假设e∈，按k，l，t的奇偶性进行讨论.

情形1 若k，l，t这三者的奇偶性相同.

不失一般性，不妨假设k，l，t均为偶数，此时Hn＝φ，从而有pn（G）＝0.

情形2 若k，l，t这三者的奇偶性不完全相同.不妨设x＝l，y＝t为偶数，k为奇数.

若e在x 到y 的长为k 的路中，则G－e不是TU－子图；若e在x 到y 的长为l或t的路中，则G－e是G 的恰有一个奇单圈分支的TU－子图，故W（H）＝4.综上

由定理1和定理2可知，对于非二部双圈图，pn（G）的绝对值有最小值16.由定理1和r≥3，s≥3可知，当r＝4或s＝4时，pn（G）的绝对值取到最小值16，即非二部双圈图的pn（G）的绝对值取到最小值16时，第一类双圈图B1（n）必含有1个C4圈和1个奇单圈；由定理2可知，当x＝1，y＝3或x＝2，y＝2时，pn（G）的绝对值取到最小值16，即非二部图pn（G）的绝对值取到最小值16时，第二类双圈图B2（n）必含有1个C4圈和1个奇单圈.同时，由以上定理可知，双圈图的无符号拉普拉斯特征多项式的常数项只与圈长的奇偶性有关.

［1］Cvetkovi D，Rowlinson P，Simic S.Signless Laplacian of finite graphs［J］.Linear Algebra and its Applications，2007，423（1）：155－171.

［2］Wang J F，Huang Q H.Some results on the signless Laplacians of graphs［J］.Applied Mathematics Letters，2010，23（9）：1045－1049.

［3］Mirzakhah M，Kiani D.Some results on signless Laplacian coefficients of graphs［J］.Linear Algebra and its Applications，2012，437（9）：2243－2251.

［4］Oliveira C S，Maia de Abreu N M，Jurkiewicz S.The characteristic polynomial of the Laplacian of graphs in（a，b）－linear classes［J］.Linear Algebra and its Applications，2002，356（1／2／3）：113－121.

［5］He C X，Shan H Y.On the Laplacian coefficients of bicyclic graphs［J］.Discrete Mathematics，2010，310（23）：3404－3412.

［6］Mohar B.On the Laplacian coefficients of acyclic graphs［J］.Linear Algebra and its Applicatons，2007，422（2／3）：736－741.

［7］Ilic A，Ilic M.Laplacian coefficients of trees with given number of leaves or vertices of degree two［J］.Linear Algebra and its Applications，2009，431（11）：2195－2202.

［8］Stevanovic D，Ilic A.On the Laplacian coefcients of unicyclic graphs［J］.Linear Algebra and its Applications，2009，430（8／9）：2290－2300.

［9］陈永玲，何常香.二部双圈图的拉普拉斯系数［J］.上海理工大学学报，2012，34（5）：481－486.