图的邻接谱半径与Harary指数

VIP免费

3.0 赵德峰 2024-11-19 6 4 551.91KB 38 页 15积分

侵权投诉

摘要

图谱理论是图论研究的一个非常活跃的领域,它以代数理论、分析理论、矩阵

理论等为基础研究图论问题.经过近数十年的研究,人们对图谱理论的认识已经

相当广泛和深入了.图谱理论所研究的对象包括图的邻接谱、拉普拉斯谱、规范拉

普拉斯谱、Q-谱等.在图的谱理论中,对图谱与图的结构性质之间的关系的研究是

该领域的核心问题之一.

图的邻接谱指的是图的邻接矩阵的所有特征值的集合,而邻接谱半径则是指

图的邻接矩阵的最大特征值.图的邻接谱半径在其相应网络的病毒传播建模中有

着很大的作用，病毒传播理论表明图的邻接谱半径越小,其抵制病毒传播的能力越

强，因此将具有某些共同性质的特殊分子图按其邻接谱半径排序,就成了很多图论

工作者研究的对象.

图的 Harary 指数是指化合物分子图中所有的节点对的距离的倒数之和,它与

化合物的很多物理化学性质有密切的联系,例如化合物的沸点等.关于图的 Harary

指数的研究也是组合化学研究的重要方向之一.

本文研究了给定点数和控制数的图类(包括树与单圈图)的邻接谱半径的排序

问题.关于给定点数和控制数的图类谱半径问题,也曾经有学者研究过,如

Stevanovic D(文[39])就描述了控制数固定的图类和控制数固定的连通图类中邻接

谱半径达到最大的图.在本文中主要研究的是树和单圈图中邻接谱半径的极值问

题.另外,我们还将图谱中的一些研究方法运用到 Harary 指数的研究中,并取得了

一系列非常有趣的结论.本文主要内容如下:

在第一章引言中,我们给出了图谱的有关定义,符号及记号,并综述了图谱研

究的历史及现状,介绍了前人关于谱半径研究的一些成果.在本章第三节中列举

了本文的主要结论.

在第二章中,我们用





(

 

max 12, 2 1n



 

且

3



)表示阶数为

,控制数

为



的树的集合.借助有关移边定理,通过定义一种新的移边运算,我们给出了





中谱半径前三大的图以及它们的谱半径.

在第三章中,我们用

   

, 2U n n

 



表示阶数为

,控制数为



的单圈图的集

合.在本章中,我们确定了

( , )U n



中的谱半径最大的图及它的谱半径.

在第四章中,记Harary 指数为图中所有无序顶点对之间距离倒数之和.在本

章中,我们研究图的嫁接与移边变化对图的 Harary 指数的影响.

关键词：邻接谱半径树单圈图控制数 Harary 指数

ABSTRACT

The theory of graph spectra is an active field in graph theory, which is based on

algebra theory, analysis theory and matrix theory. Through nearly ten years of research,

people’s cognition about graph spectrum theory is very widely and deeply. The subject

of graph spectra theory includes the adjacency spectra, Laplacian spectra, normalized

spectra and Q-spectra, etc. One of the main problems of graph spectra theory is to

determine the relationship between graph spectra and its structure.

The spectrum of graph is defined as the set of all eigenvalues of adjacency matrix,

and the largest eigenvalue is called spectral radius. The spectral radius of graph have

great function in establishing virus spread model for the corresponding network, virus

spread theory shows that more smaller the spectral radius of graph, more stronger the

resisting ability of virus spread, so sorting the special molecule figures which have

certain common nature according to their spectral radius become the researching object

of many graph theory workers.

The Harary index of graph is defined as the sum of the reciprocal distances of the

vertices of molecule figure of chemical compound, which has closely connection with

the physical chemical properties of chemical compound, such as boiling point. An

important direction to study the combinatorial chemistry is to research the Harary

index.

This paper is focus on sorting spectral radius of graphs(containing trees and

unicyclic graphs) with given order and domination number. Spectral radius of graphs

with given order and domination number are studied by scholars, such as Stevanovic D.

(seeing the reference [39]) characterizes the graphs which achieve the maximum value

of the spectral radius of the adjacency matrix in the sets of all graphs with a given

domination number and graphs with no isolated vertices and a given domination number.

In this paper, the focus is the extreme value problem of spectral radius of trees and

unicyclic graphs. In addition, applying the research methods of graph spectrum theory

to Harary index study, we win a series of very interesting conclusions. The main results

are as follows:

In the first chapter, introduction, we give some basic definitions, symbols and

notations about graphs spectra. We also reminisce the history and the state of the theory

of graphs, and introduce some important known results about the spectral radius of

adjacency of graphs. In the section 3, we list the important results of the paper.

In Chapter 2, we use





(

12 



2



) to denote the set of trees with

vertices and domination number



. In this chapter, we use the theorems of moving

edges, construct a new operation of moving edges, give the first three largest spectral

radius in the class





, together with the corresponding graphs.

In Chapter 3, we use

  

, 2U n n

 



to denote the set of unicyclic graphs with

vertices and domination number



. In this chapter, we find out the largest spectral

radius in the class

 

,U n



together with the corresponding graphs.

In Chapter 4, the Harary index is defined as the sum of the reciprocal distance for

all distinct vertices . In this chapter, we investigate how the Harary index behaves when

the graph is perturbed by grafting or moving edges.

Key words: Spectral radius, Tree, Unicyclic graph, Domination

number, Harary index

摘要

ABSTRACT

第一章绪论................................................................................................................. 1

§1.1 基本概念与记号............................................................................................... 1

§1.2 相关领域的研究进展....................................................................................... 3

§1.3 本文的主要研究结果....................................................................................... 6

第二章控制数固定树的邻接谱半径........................................................................... 9

§2.1 准备工作........................................................................................................... 9

§2.2 主要结果及证明............................................................................................. 10

第三章控制数固定单圈图的邻接谱半径................................................................... 17

§3.1 准备工作......................................................................................................... 17

§3.2 主要结果及证明............................................................................................. 18

第四章嫁接、移边对图的 Harary 指数的影响.......................................................... 24

§4.1 嫁接运算对连通图 Harary 指数的影响........................................................ 24

§4.2 移边(从一点到另一点)对连通图 Harary 指数的影响................................. 28

总结............................................................................................................................... 31

参考文献......................................................................................................................... 32

在读期间公开发表的论文............................................................................................. 35

致谢............................................................................................................................. 36

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

15 积分 4人已下载

立即下载 VIP免费下载

摘要：

摘要图谱理论是图论研究的一个非常活跃的领域,它以代数理论、分析理论、矩阵理论等为基础研究图论问题.经过近数十年的研究,人们对图谱理论的认识已经相当广泛和深入了.图谱理论所研究的对象包括图的邻接谱、拉普拉斯谱、规范拉普拉斯谱、Q-谱等.在图的谱理论中,对图谱与图的结构性质之间的关系的研究是该领域的核心问题之一.图的邻接谱指的是图的邻接矩阵的所有特征值的集合,而邻接谱半径则是指图的邻接矩阵的最大特征值.图的邻接谱半径在其相应网络的病毒传播建模中有着很大的作用，病毒传播理论表明图的邻接谱半径越小,其抵制病毒传播的能力越强，因此将具有某些共同性质的特殊分子图按其邻接谱半径排序,就成了很多图论工作者研究...

展开>> 收起<<

图的邻接谱半径与Harary指数.pdf

共38页,预览4页

还剩页未读，继续阅读

图的邻接谱半径与Harary指数

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

推荐作者

热门标签

举报选择: