文摘

让是一个简单图顶点,让其邻接矩阵的特征值;埃斯特拉达指数图的被定义为条件的总和,。的维折叠超立方体网络是一个重要的和有吸引力的变体维超立方体网络,这是获得通过添加任何一对顶点之间优势互补的边缘。在本文中,我们建立了显式公式计算埃斯特拉达折叠超立方体网络的指数通过推导光谱图的邻接矩阵的特征多项式理论。此外,一些低和上界埃斯特拉达折叠超立方体网络的指数提出了。

1。介绍

复杂网络已经成为多学科研究的一个重要领域,涉及数学、物理学、社会科学、生物学等理论和应用科学。众所周知,互连网络并行通信系统中起着重要的作用。一个互连网络通常由一个连通图模型,在那里表示处理器和的集合表示一组处理器之间的通信链接网络。让是一个图的顶点标签。的邻接矩阵的是一个矩阵的如果顶点进口等于1和否则是相邻和0。的光谱其邻接矩阵的谱,由数字吗。在这个工作我们关心有限简单无向连通图(网络)。基本图理论的定义和符号我们遵循1]。

的能量图(2)被定义为

另一个graph-spectrum-based不变,最近提出的埃内斯托埃斯特拉达,被定义为 这张图不变首次出现在2000年,在一篇由埃斯特拉达(3),处理蛋白质分子的折叠。埃斯特拉达Rodriguez-Velazquez显示提供了一个测量中心的复杂(沟通、社交、代谢等)网络(4,5]。

表示由的谱图的时刻。泰勒展开的,我们有以下重要的关系埃斯特拉达指数和光谱的时刻:

在这一点上应该召回(4),的数量等于自动回位的长度吗图的。最初几个光谱的时刻图与边缘和三角形满足以下关系4]:

为,让程度的顶点在。第一个萨格勒布指数(6图的)被定义为: 在哪里和五角大楼的数量和所有吗,是一个三角形组成的子图的数量附带一个悬而未决的顶点(7]。

超立方体的是一个最流行的和高效的互联网络由于其许多优秀的表演一些实际应用。有大量的文献在超立方体网络的属性8- - - - - -11]。作为重要的变体,折叠超立方体网络,Amawy和Latifi提出的8),得到的图形通过添加任何一对顶点之间优势互补的地址。折叠超立方体获得相当大的关注由于其完美的属性,如对称性、常规结构,强大的连通性,小直径,和它的许多特性研究[12- - - - - -19]。

本文的其余部分组织如下。节2,我们提出一些基本的符号和一些预赛在我们讨论。我们的主要结果的证明3并给出一些结论4,分别。

2。符号和一些预赛

在本节中,我们介绍一些基本的属性将被用于我们的主要结果的证明。

让邻接矩阵的特征多项式的折叠超立方体;所示的结果(12]。

引理1(见[12])。的邻接矩阵的特征多项式()是

引理2(见[12])。为与邻接矩阵的谱如下:
(1)如果(国防部2),
(2)如果(国防部2), 在哪里二项式系数和元素的第一行和第二行是邻接矩阵的特征值的分别和相应的多样性。

引理3(见[20.])。两偶图的特征值满足配对属性:,。因此,如果图是双方的,如果是无效的(其特征值为零)的多样性,然后呢 在哪里代表双曲余弦,而表示所有的积极特征值总和对应的图。

引理4(见[21])。让有一个图表边缘。为, 与人人平等当且仅当由的副本并可能孤立的顶点和人人平等奇数当且仅当是一个由两部分构成的图。

下面的引理是立即的结果之前的引理。

引理5(见[22])。让是一个图与边缘。为, 与人人平等当且仅当由的副本并可能孤立的顶点和人人平等奇数当且仅当是一个由两部分构成的图。

引理6(见[23])。让正则图的学位和的秩序。然后埃斯特拉达指数是有界的 平等拥有当且仅当。

引理7(见[23])。埃斯特拉达指数和能量图满足如下不等式: 和双方的平等当且仅当。

3所示。主要结果

3.1。埃斯特拉达指数折叠超立方体网络

在本节中,我们提出一些明确的埃斯特拉达指数计算公式。为了方便起见,我们假设如果或。

定理8。对于任何与,然后(1) ,,如果 2 (mod);(2) ,,如果 (国防部2),在哪里和或是相邻矩阵的特征值的和表示二项式系数。

证明。由引理1,相邻矩阵的特征多项式是
通过计算特征值的特征多项式及其多样性,我们获得的(1)如果(国防部2),有不同特征值,多样性,在那里;(2)如果(国防部2),有不同特征值,多样性,在那里。
结合埃斯特拉达指数的定义,我们导出定理的结果8。

3.2。一些边界埃斯特拉达折叠超立方体网络的指数

众所周知,有顶点。让的特征值与nonincreasing秩序。为了获得埃斯特拉达指数的范围,我们证明一些结果利用算术和几何平均不等式;在我们的证据,一些技术(22被称为。

定理9。对于任何与,一个 在哪里,,和五角大楼的数量和所有吗,是一个三角形组成的子图的数量附加一个悬而未决的顶点。

证明。为了获得的下界埃斯特拉达指数,认为
注意的是,,,,,我们获得
由引理5, 我们可以得到, 在哪里,,和五角大楼的数量和所有吗,是一个三角形组成的子图的数量附加一个悬而未决的顶点。
至于条款的算术和几何平均不等式,这一事实, ,等号成立当且仅当在哪里。
结合平等(19)和(20.), 在哪里,,和五角大楼的数量和所有吗,是一个三角形组成的子图的数量附加一个悬而未决的顶点。
注意,平等的21)的等式成立当且仅当(19)和(20.)持有;即平等拥有当且仅当,这是不可能的与。因此,这意味着定理的结果9。

我们现在考虑埃斯特拉达指数的上界如下。

定理10。对于任何与,一个

证明。根据埃斯特拉达指数的定义
注意到的不平等 用不平等(24)(23)我们获得
因为拥有平等, 因此, 很明显,平等的25)将获得当且仅当这个图反过来,没有非零特征值,这只发生在edgeless图吗;是不可能的与直接导致的不平等(27)。
因此,我们可以获得埃斯特拉达指数的上界: 定理的证明10就完成了。

备注11。在[23),这是证明 与平等,当且仅当。

注意到的谱半径是和;应用引理6,我们也给上下边界连接通过简单的计算及其谱半径,任何的平等是不可能的;因此

3.3。一些属性埃斯特拉达指数涉及的能量

在本节中,我们研究埃斯特拉达指数和能量之间的关系。我们首先证明埃斯特拉达的下界,涉及能源指数;在定理12证明,一些技术(23被称为。

定理12。对于任何与,一个

证明。假设表示数量的积极特征值;我们开始与埃斯特拉达指数的定义: 自平等,当且仅当,我们有
另一个潜在的不平等与平等拥有当且仅当;我们得到了
用不平等(33)和(34)(32),
请注意,
从上面的不平等(35)和(36),我们到达 当且仅当与平等是一个空图顶点,这是不可能的。
因此, 根据需要。

我们现在得到的上界,涉及能源埃斯特拉达指数。

定理13。对于任何与,一个

证明。我们考虑到
考虑图的定义能量方程(1),我们得到
的不平等(24)适用于整数,我们获得
用(26)(42),我们得到 当且仅当与平等是一个空图顶点,这是不可能的。
从上面的论点,我们得到定理的结果13。

4所示。结论

本文的主要目的是调查埃斯特拉达指数与;我们建立了明确的埃斯特拉达指数计算公式通过推导光谱图的邻接矩阵的特征多项式理论。

此外,一些低,埃斯特拉达指数上界提出了利用算术和几何平均不等式。埃斯特拉达的上下界限指标涉及的能量也获得了。

利益冲突

作者宣称没有利益冲突有关的出版。

确认

刘贾的工作包支持中国安徽省自然科学基金批准号下KJ2013B105;翔凤锅的工作是由美国国家科学基金会资助下的中国10901001,11171097,11371028。