2020年12月Dec., 2020
运筹学学报
O p e r a t i o n s R e s e a r c h T r a n s a c t i o n s
第24卷第4期
V o l.24N o.4
D O I:10.ki.issn. 1007-6093.2020.04.011
余桂东1A t阮征1舒阿秀1于涛1
摘要设G是一个n阶单圈图，M G)、乂(G)分别为图G的邻接矩阵的最大特征值与次大特征值，/x J G)、分别为图G的拉普拉斯矩阵的最大特征值与次大特征值。图G
的分离度定义为乂4(G) = A j G)—A2(G)，拉普拉斯分离度定义为S i_(G) = /M G)—
研宄单圈图的（拉普拉斯）分离度，并分别给出了取得次大分离度和次大拉普拉斯分离度的
极图。
关键词单圈图，分离度，拉普拉斯分离度
中图分类号0157
荸荠削皮机
2010 数学分类号 05C50, 05C45, 05C35
T h e seco n d m axim u m(L ap lacian) sep arator
o f u n icyclic graphs*
燃料棒Y U G u id o n g^t RU AN Zheng1SHU A x iu1Y U Tao1
Abstract L e t C b e a unicyclic g r a p h o f o r d e r n, A i(G)a n d A2(C)b e t h e largest
e i g e n v a l u e a n d s e c o n d largest e i g e n v a l u e o
f t h e a d j a c e n t m a t r i x o f G,/xi(G) a n d^2{G)
b e t h e largest e i g e n v a l u e a n d s e
c o n
d largest
e i g e n v a l u e o
f t h e L a p l a c i a n m a t r i x of G,
respectively. T h e s e p a r a t o r o f (7 is d e f i n e d a s S U((7)=入i((7)—入2(G). T h e L a p l a c i a n
s e p a r a t o r o f G is d e f i n e d a s S l(G)= ^i\(G)— ^(G).I n this p a p e r,w e s t u d y t h e
(L a p l a c i a n) s e p a r a t o r o f unicyclic g raphs, a n d give t h e e x t r e m a l g r a p h s w h i c h attain t h e
s e c o n d m a x i m u m s e p a r a t o r a n d s e c o n d m a x i m u m L a p l a c i a n s e p a r a t o r respectively.
Keywords unicyclic g r a p h, separator, L a p l a c i a n s e p a r a t o r
Chinese Library Classification 0157
2010 M athem atics Subject Classification 05C50, 05C45, 05C35
本文所讨论的图均为有限简单连通图。设G=(V，E)为n阶简单连通图，V =
V(G)= {w a,... ,%}，E=f；(G) ={ei，e2,…，em}，如果 m=n，则称 G 为单圈图。我
们记木1为所有n阶单圈图的集合，欠…、分别为n阶完全图、星图、圈
和路。
图G的邻接矩阵为ri阶矩阵4(G) = (aij)…x…，其中，当叫％相邻时，％ = 1，否
收稿日期：2018~03~21
*基金项目：国家自然科学基金（N o.11871077)，安徽省自然科学基金（NO.1808085MA04)，安徽省高
校自然科学基金（NO.KJ2017A362)
1.安庆师范大学数理学院，安徽安庆246133; School of M ath em atics and Physics, A nqing N orm al University, A nqing 246133, A nhui, C h in a
2.合肥幼儿师范高等专科学校公共教学部，合肥230013; D e p artm en t of Public E ducation, Hefei Preschool E ducation College, Hefei 230013, C hina
t通伯作者E~mail:
4期 单圈图的次大（拉普拉斯）分离度 129
贝l j ay = 0。图G的度对角矩阵为D(G) =diag(d(vi)，咖2),…，d(t/n))，其中d(Wi)表示 顶点％的度数,i= 1，2,…，n。图G的拉普拉斯矩阵定义为L(G) =D(G)-4G)。简称 4(G)的特征值为图G的特征值，L(G)的特征值为图G的拉普拉斯特征值。显然,4(G)和 L(G)为实对称矩阵，故其特征值均为实数，可分别排列成>A2(G)彡…彡A“G), Mi(G〇 >P2(G) > …>m«(G)»〇，其中 \(G)为 A(G)的第 i 大特征值，Mi(G)为 L(G)的第i大特征值。图G的分离度[1]定义为心(G) =A d G)-A2(G)。图G的拉普拉斯分 离度[1]定义为 5L(G) =Ml(G)-A t2(G)。 最近，关于图的分离度、拉普拉斯分离度和无符号拉普拉斯分离度的研究己有一些 成果。如文[1]研宄了树与单圈图的最大分离度和最大拉普拉斯分离度；文[2]研宄了单圈 图、双圈图和三圈图的最大无符
eps复合保温板号拉普拉斯分离度；文[3]研究了连通图的最大与次大拉 普拉斯分离度；文⑷研究了给定阶数的双圈图和三圈图的最大拉普拉斯分离度.受这些 研宂的启发，本文用相似的方法研宄了单圈图的（拉普拉斯）分离度，并分别给出取得次 大分离度与次大拉普拉斯分离度的极图。
1 准备工作
我们记n阶最大度为n-1的唯一单圈图为[/…，即[/…是由增加一条边所
得的图.
引理l W若彡8时，知(G)彡义(％)，等号成立当且仅当G=t/…。
我们记n阶最大度为n-2的三个单圈图分别为以、巧、巧，如图1所示。
K U2n Ul
图1的、扣、扣
引理2间单圈图的最大特征值序（n> 12)如下：
A1(C/…)>A1(^)>A1(f/i)>..-
引理3间设n彡8，若G为n阶连通单圈图，且G荖C/n，则A2(G)彡1，等号成立 当且仅当G S C^。
假设G i和G2为两个顶点集不相交的图，其中外e V^GG，巧e V(G2)。图G i和G2的黏合记为 G(巧）•G2(u2)，其中 (仍）•G2(i;2)) =W G O U F(G2)U{t>*}—{外，仍}，中的两个顶点相邻，当且仅当它们在G i或G2中相邻，或者，如果一个顶 点是必则另一个顶点和^或相邻W。4(G)表示4(G)中删掉顶点u所在行所在列 后得到的主子矩阵，记 =det[；r J-A(G)]，％[人(G);a;] =d e t[x J-人(G)]。Z^G) 表示L(G)中删掉顶点r所在行所在列后得到的主子矩阵，记$2(G; a;)=det[a;J-L(G)]，^2[L v{G)-,x\ =det[x/ —L v(G)}〇
130余桂东，阮征，舒阿秀，于涛24卷引理4设01(^1卜02(的）如上述定义，则有
^i(G i(t；i)•G2(v2)',x) =^i(G i；x)^>i[^2(G2);x] +^i(G2;x)^>i[A1；1(G i);x]
钝化膏
-x^i[AV l(G i);x]^>i[AV2(G2);x]〇
证明将中的顶点适当标号可得
(O r s>
rT A Vl{G x)0 ,
s T0A V2(G2))
其中r (或s)是^4(00中（或A(G2))和w(或i;2)相邻的点排成的非对角向量，则^i(Gi(t；i)•G2(v2);x) =det(xl -A(Gi(vi) •G2(v2)))
x—r—s
=—rT x l —A Vl(G\)0
_5丁0 x l一A.V2(G2)
⑴
X—r0
T
—r x l—A Vl (G i)0+
钼精粉
T
—S0xl—A V2(G2)
X0 ^>1(G i;X)$i[A V2(G2);X] +—r T xl -■^V\
-s T0
0 -s
xl —A V l(Gi) 0
0 xl —A V2(G2)
—s
Xl — A y2(G2)
—
x0 0
+_t*t x l—AV l(G^i)0
-sT 0 x l—A V2(G2)
x—s0
=少1(G i;x)少1(G2);x] +—sT x l—A V2(G2)〇
-rT 0 x I-A y^G x)
[AV l(Gi); x]^i [AV2(G2);x]
=(
G i；[^4U2(G2);a:]+^>i(G2；x)^i[AV l(G i);x] —x^\[AVl(G\)\x\^\[AV2{G2)\x]〇
引理5当n彡149时，有心(％) <
证明根据引理4，通过简单的计算，得到
x)=x n~6(x2—l)(x4-h(3 —n)x2—2x+n—7),
少1(W;a:) =xn_4(x4—na:2—2x +2n —7) 〇
令分1(工）=z4 + (3 —几)工2 —2:r+n— 7，因为分i(l) = _5 < 0，分i(0) =n—7 > 0，仍(—1) = —1 < 〇，根据其函数图象可知仍的第一大零点大于1，第二大零点小于1，这 样可得即伞第二大零点为1，即A2(C^) = 1。又因为当n彡25时，=几一2\/^^-7>〇，仍—3 <0，所以仍(x)的最大零点介于
与 y/n —3 之间，即\J V i —4 <Ai(U^)<y/n — 3〇由此，可得>y/n —4—1。
4期单圈图的次大（拉普拉斯）分离度131
同理可令分2(x) =z4—na;2—2a:+2n—7，经计算得当n彡I49时，分2(_2) =I3—2打< 〇, 52(1.4)=蟲—> 0，52(1.5)=〒—H< 〇，g2W n ~2) = —2\/n—2 — 3 < 0, 92W n ~1)=n - 2\Jn -1 -6 >0，再根据真图像可知仍(〇;)的第一大零点介于如―2 与之间，第二大零点介于1.4与1.5之间，即<v^X 1.4 < A2(C^) < 1.5。由此，可得 SA(W) <_ 1.4 <- 1〈心(巧)。
引理6[8】设G是一个ri阶非平凡简单图，// =G-e是由图G删掉一条边所得到 的图，则有
^l(G) ^ fX\{H)^A*2(G) ^ ^ ^ f J，n(G)^fln(H)= 0〇
引理7W
<I,2(-K'l,n；x) =x(x-n-l)(x-l)n_1;
企2[k2(心,n);X] = (X-1广，其中仰是A V的中心；
^2(C3;x) =x(x-3)2;
= (a;-l)〇c—3)，其中i»i 是C3 的某个顶点。
引理 8W当n彡 5 时，SL(t/…)=n-3。
引理9間设G是一个n阶简单图，则
/i i(G)<m a x {d(W i) + m(V i)}，
l^i^n
其中 m(i；i)=E d H
WiUje£(G)
弓丨理l〇l1Q丨设G(外）•G2(t;2)如上述黏合所定义，则有
$2(G i(u i) •G2(v2);x) =$2(G i；x)$2[^t；2(G2)；a:] +^2(^2； a;)$2[^Ul (G i); x]
引理 11 当n>11 时，&(矻）<SL(C^) <n-4 <&(C^)。
h
证明我们把巧、吒、叼分别看作由<73的某个顶点巧与图2中F12的a点黏 合，心…_4的中心点巧与图3中巧3的6点所黏合，以及尺M-4的中心巧与C4的某 个顶点M点黏合得到的。
132余桂东，阮征，舒阿秀，于涛24卷根据引理7和10，通过简单的计算，得到玻璃夹胶机
^2(^n；—l)n_5(x—3)(x3—2x2—nx2-h3nx — 2x —n),
^>2(^n5x) =x(x ~l)n-5(^4 —5x3 —nx3-1-3x2+6nx2+5x—9nx+3n),
少2(W；工）=工(工—l)n—5(工—2)(x3—3x2—nx2+4nx—2x—2n)〇我们令 /i(x) =a:3—2x2—nx2+3n:r—2:r—n，则 /{⑷=3x2—(2n+4)x+3n—2，通过
计算可得 /(〇r)的 2 个零点分别为 a =(n+2)—5n+1卫 < 3 和 a r2 = ("+2)+V^-5n+io > n —1，则可得当；r >a；2或a; <a r!时八⑷单调递增，当：T i<x <；工2时/i(:e)单 调递减。而当n彡11时，有^(3) = 3-n < 0，这样根据图像的单调性知AOr)的第二大零点小于3，第一大零点大于n — 1> 3。即//2(巧）=3,m i(巧）>n - K故 S L{Ui) = /ii(f/2) - M2([/3) > n _4〇
同理可令 /2(a;) =a;3—3;e2—n;r2+4na:—2a:—2n，算得 /《(a:) =3;r2—(2n +6)a:+4n —2，得乃〇r)的 2 个零点分别为灼=(n+3)-^-6«+15 < 3.3 和叼=(n+3) +^-6n+15 <n_L 而当 n彡 11 时，/2(3.3) > 0,/2(n—1) = -2 < 0,/2(n-0.8) =0.2n2 —1.12n—0.832 > 0，则根据单调性知/2(a〇的第一大零点小于n_0.8，
第二大的零点大于3.3，则有$2(巧;
的第一大零点小于n—0.8，第二大的零点大于3.3，即/^(巧）<n_0.8, /x2(Lg) > 3.3。所 以 5以[^) <n-4.1<n—4<；扣）。
^/a(^) =x4—5x3—nx3 +3x2 +6nx2 +5x— 9nx+3n,f i{x) =(x— 2)(x3—3a:2— nx2+
4n;r-2x-2n), /5(;r) =/3(x)—/4(x) =—(a;—l)(a;-n)，则当 1 <x<n 时，有 /5(;r) >0，而由前面的证明可知/4〇c)的第一大的零点小于n-0.8，第二大的零点大于3.3，又通过 计算可得当 n > 5 时，/3(0) =3n>0，/3(1) = 4 —n <0, /3(3.3) >0, /3(5) = 100 —17n<0, /3(n-0.8) >0，所以/3(a:)的第二大的零点大于3.3, /3⑷的第一大的零点小于n-0.8，这样根据函数图象可得/3〇r)的第一大的零点与第二大的零点的距离小于/4〇r)的第一 大的零点与第二大的零点的距离，g卩，当n>11时，
综上得证，当n彡11时，知(巧）<；知(巧）<n—4 <；知(扣)。
2主要结论
定理1设n彡I49，且G e 乂…\[/…，则心(G) <；心(扣)，且等号成立当且仅当G=巧。
证明根据引理2和3可得，当G关％且G荖巧时，A2(G)彡1 =A2(扣)，A:(G) < M扣)。所以G关t/…且G关的时，S a(G) < 5A(f^)，再由引理1和引理5，知心(巧）< SA(C/)) <SA(C/…)，综上得证。
我们称图G中最短圈的长度为图G的围长，记为s(G)。记A(G)是图G的最大度。下 面首先介绍两类特殊单圈图，记所有9(G) =3的6阶单圈图分别为R、F2、F3、F4、f5、凡、朽，如图3所示；记所有g(G) =4的6阶单圈图分别为F8、凡、朽〇、P u，如图4所示。
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议