火图的Aα-特征多项式的部分因子分解及特征值

可在www.sciencedirect.com在线获取理论计算机科学电子笔记346（2019）209-219www.elsevier.com/locate/entcsFire图的α而我是布朗达尼1号巴西里约热内卢弗鲁米嫩塞联邦大学数学系卡拉·席尔瓦·奥利维拉2国立统计科学巴西里约热内卢Francisca Andrea Macedo Franca3巴西里约热内卢弗鲁米嫩塞联邦大学数学系Leonardo de Lima4生产工程系巴西里约热内卢联邦技术教育中心摘要设G是n阶连通图，A（G）是G的邻接矩阵，D（G）是A（G）的行和的对角矩阵. 在2017年，Nikiforov[8]定义了A（G）和D（G）的凸线性组合Aα（G）：A α（G）=αD（G）+（1−α）A（G），0≤α≤ 1。本文得到了火图的Aα-特征多项式的一个部分因子分解，它显式地给出了火图的一些特征值关键词：特征值，Aα矩阵，火图1电子邮件地址：andrebrondani@id.uff.br2电子邮件：carla. ibge.gov.br3电子邮件：francisca franca@id.uff.br4电子邮件：leonardo. cefet-rj.brhttps://doi.org/10.1016/j.entcs.2019.08.0191571-0661/© 2019作者。出版社：Elsevier B.V.这是一篇基于CC BY-NC-ND许可证的开放获取文章（http://creativecommons.org/licenses/by-nc-nd/4.0/）。210A.E. Brondani et al. /Electronic Notes in Theoretical Computer Science 346（2019）209222n−11引言设G是一个n阶简单图，其顶点集V（G）和边集E（G），使得|E（G）|=m。 我们用Kn表示n个顶点的完全图。 集合G中顶点v的邻点的个数记为NG（v），且NG[v] = NG（v）<${v}. G的顶点v的degre，d（v），定义为：|NG（v）|. 两个不同的顶点u和v在G中被称为真孪生，如果NG[u] =NG[v]，并且被称为假孪生，如果NG（u）=NG（v）并且u不与v相邻，参见[7]。G的无符号Laplacian矩阵定义为Q（G）=A（G）+D（G），其中D（G）是度的对角矩阵，A（G） =[aij]是G的邻接矩阵，其中 ai j=1i 如 果 vi 与vj 相邻 ，否 则 ai j=0. 最近 Nikiforov [8] 定义 为任 何真 正的α∈[0，1]，A（G）与D（G）的凸线性组合Aα（G），A α（G）= αD（G）+（1 −α）A（G）.很容易看出A（G）= A0（G），D（G）= A1（G）和Q（G）= 2A1（G）。 Aα-2G的特征多项式定义为PAα（G）（x）= det（Xiα（G）），根称为Aα（G）的特征值。通常，我们将Aα（G）的特征值按非增阶指数化，记为λ1（Aα（G））≥λ2（Aα（G））≥·· ≥λ n（A α（G））。A α（G）的谱定义为特征值的多重集及其代数重数，记为Spec（A α（G））. 为了简化，当没有歧义的风险时，我们使用Aα和λi（Aα）符号如Aouchicheet al. 图Fs，r，t是n=2r+s+ 2t+ 1个顶点上的图，它由s条垂边、r个三角形和t条长度为2的垂路组成，它们都有一个公共顶点。 设Fn是所有n阶火图的集合。 注意Fn包含星SnFs，0，0，拉伸星（Fs，0，t），友谊图（F0，r，0）和黄油图（Fs，r，0）。 研究这个家庭的意义在于， 许多依赖于图矩阵特征值的函数的极图都属于Fn。对于单圈图，Hong [4]确定了A（G）具有最大特征值的唯一图Fn −3，1，0。Fan等人[2]确定了当n ≥ 12时，在所有n阶单圈图中，A（G）的最小特征值最小的唯一图Fn −3，1，0。 Petr ov i'cetal. [9]确定了在n个顶点（n≥12）和k个圈的仙人掌中A（G）的最小特征值最小的唯一g∈Fn-3，1，0，其中0≤k≤[-是的Li等[6]刻画了图Fn-[n-1<$-1，[n-1<$，0]，在所有的无符号Laplacian谱半径中，n顶点仙人掌。在这里，我们解决的问题，找到所有的特征值的A α（Fs，r，t），这填补了文献的空白，推广的特征值的邻接和无符号拉普拉斯矩阵的一个方便的α。本文的组织方式是在下一节中介绍初步结果，主要证明在第3节中。A.E. Brondani et al. /Electronic Notes in Theoretical Computer Science 346（2019）209211⎢⎥⎢⎥M=,.Σ.⎢.. . . . ⎥（ii）Spec（Aα（Sn））=1（αn+β），α[n−2]，1（αn−β），其中β=1αn1αn√u∈V（G）2结果分析首先，给出了Horn和Johnson[5]中的矩阵的公平分划定理，以及分别给出Aα（Kn），Aα（Sn）的特征值和λ1（Aα）的上界的命题2.2和2.3命题2.1（[5]）设M是一个n阶矩阵，定义为M1，1M1，2···M1，kM2，1M2，2···M2，kMk，1Mk，2 ···Mk，k其中Mi，j，1 ≤ i，j ≤ k，是n i× n j阶的子矩阵，使得它的每一行的和等于ci，j。若M= [ci，j] k×k，则M的特征值也是M的特征值。命题2.2（[8]）对于α∈[0， 1]，有（i）Spec（Aα（Kn））={n−1，（αn−1）[n−1]};2 2α2n2+ 4（n − 1）（1 − 2 α）。命题2.3（[8]）如果G是n阶图，有m条边，则λ（A（G））≥λ。，1个月d2（u）和λ（A（G））≥2m.第二个不等式成立，当且仅当G是正则的。 如果α> 0，则第一个不等式成立当且仅当G是正则的。命题2.4指出，G中孪生顶点的存在意味着Aα（G）的谱中存在某些特征值λ，并且还提供了这些特征值的重数m（λ）命题2.4设G是n ≥ 2个顶点的图，其中vi和vjp，1 ≤ p ≤ r是G中的孪生顶点.(i) 若vivjp，则αd（vi）∈ Spec（A α（G））且m（αd（vi））≥ r.(ii) 若v i<$v jp，则α（d（v i）+1）− 1 ∈ Spec（A α（G））且m（α（d（vi）+1）− 1）≥ r。证据 对于给定的p ∈ {1，2，...，r}，设v i和v jp是G中的孪生顶点. 考虑向量x（p）∈Rn，212A.E. Brondani et al. /Electronic Notes in Theoretical Computer Science 346（2019）209⎪⎨nppp⎨啪啪啪啪如果vi= 0，则αd（vi）x（p）pVJP.[x（p）]k=如果k=i，则 为n = 1;−1，如果k=jp;000， 否则。由于A α（G）= A α，我们有，对于每个l ∈ {1，2，.， n}，[Aαx（p）]l=<$[Aα]l k[x（p）]k=[Aα]li−[Aα]lj.（一）k=1现在，考虑以下三种情况：情况1l = i. 在这种情况下，所以，[Aαx（p）]i=[Aα]ii−[Aα]ij=αd（vi）−[Aα]ij，情况2l = j p。在这种情况下，[Aαx（p）]i=<$α（d（vi）+ 1）−1，sevi<$vjp;其中，n（v i），n（v i），n（v j p），n（v i），n（vjp），n（vi），n（v jp）。并且，在本发明中，[Aαx（p）]j=[Aα]ji−[Aα]jj=[Aα]ji−αd（vj），[Aαx（p）]jp=−α（d（vjp） +1）+1，如果vivjp;情形3l∈/{i，jp}.−αd（v jp），如果v iv jp。由于vi和vjp是孪生顶点，我们有[Aα]li=[Aα]ljp。则对于方程（1）[Aαx（p）]l=0.因此，在之前的三个案例中，<$$>（αd（vi） +α−1）xp，如果vi<$vj;Aαx（p）A.E. Brondani et al. /Electronic Notes in Theoretical Computer Science 346（2019）209213p=1很容易看出{x（p）}r是线性无关的。 因此m（λ）≥r，对于λ∈ {αd（vi），αd（vi）+α−1}。Q214A.E. Brondani et al. /Electronic Notes in Theoretical Computer Science 346（2019）209⎢⎢⎥⎥⎣⎦2v2v3v4v11v9v8v1的v12v10v6v5v73主要结果在这一节中，我们提出的结果涉及的特征值的图在家庭Fn。对于满足Aα=Aα（Fs，r，t）的图Fs，r，t∈Fn，有一个方便的点标号可写为α（t+s+2r）（1−α）J1×s（1−α）J1×2r（1−α）J1×t01×tAα=α⎢⎣⎤、（二）⎥⎦哪里B2R =<$2 αIr （1 − α）Ir<$。（3）（1 − α）Ir2 αIr图1显示了采用标签的火灾图F3、2、2Fig. 1. 火灾危险图F3，2， 2注3.1设GFs，r，t，图G恰好有一个顶点的度等于2r +s+t，2r+t个顶点的度等于2，s+t个顶点的度等于1.当α= 1时，A1（G）=D（G）的特征值为d（v），v∈V（G）;当α= 0时，A0（G）=A（G）的特征值见[3]。在命题3.2中，我们能够证明一个火图的某些特征值的出现依赖于某些导出子图的存在命题3.2给定非负整数r，s和t，设GFs，r，t和α∈（0，1）. 如果t ≥2，则θ1=3α+<$5α2−8α+4且θ=3α−<$5α2−8α+4是特征值G的重数至少为t− 1。 此外，如果r≥ 2，则α + 1是一个重数至少为r − 1的特征值。22（1 −α）Js×1αIs0s×2 r0s× t0s× t（1−α）J2r×102r×sB2R02r×t02r×t（1−α）Jt×10t× s0t×2 r2αIt（1−α）It0t×10t× s0t×2 r（1−α）ItαItA.E. Brondani et al. /Electronic Notes in Theoretical Computer Science 346（2019）209215证据 给定λ ∈ {θ1，θ2}，假设t ≥ 2，对于每个i ∈ {1，2，.，t-1}，考虑216A.E. Brondani et al. /Electronic Notes in Theoretical Computer Science 346（2019）209⎩如果j=s+2r +2 +i，则为λ−λ−α;i=1具有2个r +s+2个t + 1个条目的向量x（i），其中λ−α，如果j=s+2r+2; 1−α⎪[x（i）]j=0⎪1 −α1，如果j=s+2r+t+ 2;−1， 如果j = s + 2 r + t +2 +i; 0，否则。这样，向量Aα（G）x（i）−λx（i）的元素由下式给出：Σ Σ⎧⎪⎨Jλ2−3αλ +α2+2α− 1α−1−--，如果j=s+2r+ 2;Aα（G）x（i）−λx（i）=⎪⎩λ23αλ+α2+2α1，如果j=s+ 2r +2 +i;0，否则。由于λ是多项式x2−3αx +α2+ 2α− 1的根，因此x（i）是 一个相关的特征向量为λ。由于{x（i）}t−1是线性无关集，λ的重数至少为t− 1。现在，假设r≥2，用ek表示具有s+2r + 2t + 1坐标的向量，其第k个对任意j，s+2≤j≤s+r，很容易证明向量zj=ej−ej+1+ej+r−ej+r+1是Aα（G）的与特征值α+1相关联的因此，α +1是A α（G）的重数至少为r − 1的特征值。Q注3.3如命题3.2所述，我们使用符号θ1和θ2表示多项式x2−3αx +α2+ 2α− 1的根。当s≥ 1时，GF s，0，0S s和A α（S s）的特征值可以在命题2.2中看到.命题3.4设GF0，r，0.若r≥ 1且α∈（0，1），则PAα（G）（x）=（x − α − 1）r−1（x − 3 α +1）r（x2−（2 αr + α +1）x+（6α − 2）r）.⎧A.E. Brondani et al. /Electronic Notes in Theoretical Computer Science 346（2019）20921733⎣⎦⎣⎦33333Aα（G）α此外，如果x1和x2表示PAα（G）（x）的二次因子的根，则如果0α≤1，则x2≤3α−1α+ 1x1;如果1α1，则n=3α −1≤x2< α+ 10，如果α∈（1，1）.所以很容易看出如果0α≤1，则x2≤3α−1α+ 1x1;如果1< α 1，则n=3α−1≤x2α+ 1x1等式仅在r= 1或α=1时成立。Q命题3.5设GF0，0，t。如果t≥ 1且α∈（0，1），则P（x）=（x2−3αx +α2+2α− 1）t−1h（x），218A.E. Brondani et al. /Electronic Notes in Theoretical Computer Science 346（2019）209（1α）J2αI（1⎢⎣1α2α1⎥⎦α⎧⎪x33α−1< α x2α+ 1x1,if0α≤1;min{x3，3α−1}max{x3，3α−1}< α x2α+ 1x1，if1< α 1;⎪⎩x3< α <3 α −10，对于所有t≥1，α∈（0，1），则h（x）在（θ2，θ1）中有根. 作为 limh（x）=∞且limh（x）=x→∞x →−∞−∞，前面的不等式意味着x3<θ2032x→−∞- ∞我们有x3min<32−⎥、证据 对于Gfs，r，0，我们有⎢⎡α(s+2r)(1−α)J1×s(1−α)J1×2r⎤⎥Aα（G）=−α）Js×1αIs0s×2r（1−α）J2r×102r×sB2r其中B2r是（3）中给出的矩阵从命题2.4的证明中得到的向量，可以得到r个与特征值3α− 1相关的线性无关特征向量和s−1个与特征值α相关的线性无关特征向量。根据命题3.2，α+1是重数至少为r−1的Aα（G）的特征值，并且根据命题2.1，约化矩阵的特征值M=1α α01−α01 +α其特征多项式为h（x）=x3−（αs+2αr + 2α + 1）x2+（（α2+3α− 1）（s+2r）+α2+α）x−（2α2 +α− 1）s+2αr（1− 3α）。注意h（α+ 1）= −2（α−1）2r0和h（α）=（α−1）2s>0对所有的α∈（0， 1），s1和r1。所以h（x）在（α，α+ 1）中有一个根x2。因为limh（x）=且x→∞h（α+1）0，我们得出结论，h（x）的最大根x1满足α+1 0对于一个llα ∈.0，1，1，1，1，ASlim3 2h（x）={3 α − 1，α}。同样，当α ∈。1，1α，证明了max {x3，3 α − 1} <α。很容易分类Aα（G）的特征值，结果如下。Q命题3.7设GF s，0，t。如果s≥ 1且t≥ 1，则PAα（G）（x）=（x−α）s−1（x2−3αx +α2+2α− 1）t−1h（x），其中h（x）= x4−α（s+t+4）x3+[（3 α− 1）（α+1）（s+t+1）+ α2] x2−α[（α2+ 2 α − 1）（s +2 t +1）+（2 α − 1）（3 s + t）] x+（2 α − 1）[α2（s +2t）+（2 α − 1）s]。此外，多项式h（x）有四个不同的根，x1，x2，x3和x4，使得、⎥⎦220A.E. Brondani et al. /Electronic Notes in Theoretical Computer Science 346（2019）209x4<θ20，h（θ1）=−（α−1）2t2（3α2-4α+2+α5α2− 8α+ 4）0<2（α 1）6t且h（θ2）=−3α24α +2+α<$5α28α +40，对所有α∈（0， 1），s≥1，

下载后可阅读完整内容，剩余1页未读，立即下载