文摘
考虑以下所有图有限、简单、连接、无向。图的邻接矩阵是0,1矩阵 。在这篇文章中,我们讨论了新型的邻接矩阵被定义为1 - 2邻接矩阵 ,从图的特征值,我们的意思是1 - 2邻接矩阵的特征值。让是树木的补充订单的集合 。在这篇文章中,我们一个独特的特征图的最小特征值是所有图表中最小的 。
1。介绍
让 是一个简单图的顶点集 和边集 。它的顺序是 ,用 ,和它的大小是 ,用 。两个顶点之间的距离和的图是他们之间最短路径的长度。1 - 2的邻接矩阵定义矩阵 的订单与 如果 和为零的情况。的解决方案的特征值 。自总是对称的和真实的,所有的特征值可以安排吗 。我们写的最小特征值 。一个人可以发现是完全的谱半径 。
图的最小特征值是负的。只断开连接图,它等于零。否则,对至少一个边缘图,它是小于或等于(通过交错定理,看到1),p-19);它等于当且仅当是一个独立完整的图表或联盟等价是一个零图或一个完整的多歧的图。如果包含作为诱导子图 由交错定理(再一次)。为邻接矩阵, ,如果一个图包含是一种诱导子图,然后呢 。
结果有很多文献中关于简单图的最大特征值(谱半径);见,例如,(2]或[1]。Javaid检查不同家庭的图表来选择最优图对通过通常的邻接矩阵最小特征值在各自的图类(3- - - - - -5]。Lubna hussein等人研究了平方功率图为他们的最小特征值(6]。最近,最小化的问题图的最小特征值受一个或多个参数得到了更多的关注。贝尔et al。7,8]讨论了连接图的最小特征值与规定的秩序和大小。风扇等。9讨论了树的最小特征值的补充。刘等人。10]讨论了单循环的图的最小特征值与吊坠顶点。风扇等。9]讨论了单循环的图的最小特征值与给定的周长。佩特et al。11讨论了双环图的最小特征值。
家庭的图表,图表被称为最小化如果其邻接矩阵的最小特征值最小集的最小特征值的所有图表。表示由 , 树的集合和树木的补充订单的集合n,分别。在本文中,我们确定独特的最小化图为 ,这不是恒星的补图,我们限制我们的讨论组吗在哪里表示所有的图表是 。
定理1(见[7])。如果图的最小特征值是最小的在所有的连接图,然后呢(我) 要么是两偶图吗(2) 是连接两个嵌套分割图
定理2(见[12])。让 表示所有的家庭由两部分构成的图形,让连接 图,其最小特征值是最小的在所有的连接由两部分构成的图形,然后必须是一个双嵌套的图。
2。主要结果
我们开始有一些定义。给定一个图的订单 ,一个向量 叫上定义G如果存在一个单射函数从的条目 ;简单的写 为每一个 ,如果是一个特征向量 ,那么自然上定义每一条目的对应的顶点 。一个很容易证明 和的特征值对应的特征向量敌我识别 和 在哪里表示的附近图中 。方程(2)图形的特征方程 。现在,对于任意单位向量 , 相等当且仅当是一个特征向量的 。现在,让表示一个图的补充 。一个很容易证明 ,在哪里和表示单位矩阵的矩阵相同的大小 。现在,对于任何一个向量 ,
一个图表据说树当且仅当任何一对顶点之间存在一条路径,没有循环。树是一个明星当且仅当存在一个顶点的度和其他所有顶点度1。我们介绍一种特殊的树,用 ,这是来自两个不相交的明星 和 通过加入一个吊坠的顶点和一个吊坠的顶点 。的补充 是 ,如图1。
引理1。鉴于 ,对任何正整数 这样 和 , 当且仅当与平等 和 。
证明。假设
。让的最小特征值和是相应的特征向量。让表示的条目对应顶点为
。现在,通过特征方程(2),所有的顶点连接和有相同的价值观由吗
,说和
。现在,随着
,通过一个特征方程,
变换(5)成一个矩阵方程
,在哪里
和大学入学考试订单6是省略。我们得到了
和
请注意,是根的
。此外,
作为
,这意味着
。
如果
,通过上面的讨论,
,我们有
特别是,
,这意味着
现在的结果。
引理2。让是一个图,让的特征向量 ,然后包含至少两个正面和两个负面条目。
证明。在相反的假设包含一个积极的条目对应顶点 ,也就是说, 。自不是一个明星,存在一个顶点吗 这样 。考虑到特征方程(2)的顶点的图 ,我们有 这意味着 和 为每一个 ,现在 现在,让 。然后,通过(2)和(11), 这意味着 。自 作为不是一个明星,一个矛盾,那么我们的假设是错误的,因此吗包含至少两个积极的条目。类似地,如果我们考虑 ,我们也会它包含至少两个消极的条目。结果如下。
在我们国家其他结果之前,我们需要一些定义。
让是一个两偶图与彩色类和这样 。 据说双嵌套的图如果 和 这样,每个 毗邻每个顶点在吗 ,同样的,每个 毗邻每个顶点在吗 为 。
现在,我们知道12),如果这两个顶点和属于同一类和颜色 ,然后 。
让 和 颜色类等 和 ,在那里和为 对应的特征向量的条目吗的 。
引理3(见[12])。让G图与上面的假设。然后,(1)顶点和是相邻的(2)的程度和是完整的(3)如果顶点是相邻的 ,然后是相邻的为 ,如果顶点是相邻的 ,然后是相邻的为
观察1。如果是一式两份的订单和大小
,然后去其通过增加大小的下界。
贝尔(12]讨论了最大特征值的行为通过增加边的数量和保存固定的。我们这里显示的最小特征值的行为图由固定边的数量
顶点的数量会增加。在图2顶点,水平轴和垂直轴表示最小特征值。
定理3。让是一个树 。然后,
证明。正如我们所知, 由定理1和2,这足以证明是一个最大双嵌套的图在哪里距离。让这样的图是至少有一个在所有的图表,让是最少的特征向量。现在,让图得到通过旋转的边缘来这样为 ,然后 ,同样的,如果和属于同一颜色类酸处理 ,然后度(年代)度(t),所以通过引理3,这将是一个双嵌套的图。接下来,我们将证明它是最大的可能的双嵌套的图距离。的大小是 ,所以我们需要展示的是,大小不能超过 。在相反的假设 ,然后要么 或 。在这两种情况下,连接 在距离是不可能的,这就完成了证明。
的利益冲突
作者宣称没有利益冲突。