有向图的拉普拉斯谱半径的几个上界.PDF

第39卷第6期 应 用 数 学 学 报 Vo1．39No．6 2016年 l1月 ACTA MATHEMATICAEAPPLICATAESINICA Nov．，2016 有向图的拉普拉斯谱半径的几个上界 席维鸽 王力工 (西北工业大学理学院应用数学系，西安710072) (E—mail：xiyanxwg~163．corn；tlgwangmath~163．com) 摘 要 设 G=((G)，E(G))是—个简单有向图具有顶点集 (G)：{ … }和弧集E(G)．用 d 表示顶点 的出度．设 A(G)是有向图G的邻接矩阵和 D(G)=diag(d+，d，…，d)有向图G 的顶点出度对角矩阵，则称 L(G)=D(G)一A(G)为有向图G的拉普拉斯矩阵．L(G)的谱半径称 作有向图G的拉普拉斯谱半径，用 (G)表示．在这篇文章中，给出了关于 (G)的一些上界， 进而一些关于 (G)涉及有向图G的出度和二次平均出度的上界也被得到．最后，我们举例对 这些上界进行了比较． 关键词 有向图；拉普拉斯谱半径；上界 MR(2000)主题分类 05C50；15A18 中图分类 O157．5 1 引言 设G=((G)，E(G))是一个有向图具有顶点集V(G)：{1，V2，…，”)和弧集E(G)． 如果一个有向图既没有环又没有重弧，则把它叫做简单有向图．如果对于一个有向图中 的每对顶点仇，vj∈ (G)，既有一条从Vi到 ”j的有向路又有一条从 到 Vi的有向路， 则把它称作强连通有向图．在这篇文章中我们仅考虑至少有一条弧的简单有向图． 对于一个有向图G，如果 (Vt，Vj)是 G 中的一条弧，则把 Vt叫做这条弧的起点， 叫做这条弧的终点．对于 G 中的任意一个顶点 ，我们用 = ()= {vj： (V)∈E(G))表示顶点V的出邻集．设d=l时 1表示有向图G中顶点 的出度， ￡= E d 表示顶点V的二次出度．此外，m = ／d表示顶点 的二次平均出 ”3∈N J 度． 本文 2015年 2月 7日收到．2016年 4月 25日收到修改稿 国家 自然科学基金 (No资助项 目． 十通讯作者． 802 应 用 数 学 学 报 39卷 对于一个有向图G，设A(a)=(ai)是有向图G的邻接矩阵，这里 a 等于从 到 ”的弧的数 目．设D(G)=diag(djI，d，…，姑)为有向图G的顶点出度的对角矩阵．则 矩阵L(G)=D(G)一A(G)被称作有向图G的拉普拉斯矩阵．有向G的拉普拉斯特征值 ， 。，… ， 是其拉普拉斯矩阵的特征值．一般情况下，有向图G的拉普拉斯矩阵不 是实对称矩阵，因而它们的特征值有可能是复数．我们通常假定 lI l2l … l 1． 有向图 G的拉普拉斯谱半径定义为其拉普拉斯特征值的最大模，记作 (G)，即有， (G)=lA11． 目前，关于无向图的拉普拉斯谱半径已经有很多结论，具体可见f1-6]和一个综述 (见 7『1)，但是关于有向图还没有太多的结果．最近，一些文章给出了有向图谱半径的一 些上界或下界，具体可见 f8—121．然而，一个无向图D的拉普拉斯矩阵可以被看作一个 有向图G 的拉普拉斯矩阵，这里 G通过把无向图D中的每条边用一对反向弧代替得 到．因此，对有向图拉普拉斯矩阵的研究具有更普遍的意义．基于此，我们研究有向图 的拉普拉斯谱半径．关于有向图的拉普拉斯谱半径已有以下结果： [13】把 Fiedler给出的简单图的代数连通度的概念推广到有向图上，并建立了有向 图的代数连通度与图的一些参数 (如二部宽，极大有向割)的联系． [14】得到了关于有向图拉普拉斯谱半径的以下结果． 引理 1．1【]设G是一个n阶的有向图，则 (G) max{d+d一I时 nⅣ l= 1 i，J 他}．这里l町 n l表示顶点 和Vj的公共出邻点数目． 引理 1．2[14]设 G是一个