定向图的Wiener指数和几类拓扑指数的极值问题

摘要

图G的Wiener指数定义为G中所有点对的距离和。最近Wiener指数的概念被推广到非强连通有向图中，这一推广可被应用于大规模有向网络的分析。图G的定向是对G的每条边指定一个方向得到的有向图。M.Knor等人猜想图G的极小Wiener指数可由某种x(G)导出定向取得。
　　第一章概述有向图Wiener指数的研究进展和基于度的几类拓扑指数的研究现状，提出本文拟解决的问题和取得的主要结果。
　　第二章提出I-点和Wiener增量的概念，构造了一类不满足着色导出定向猜想的图，否定了该猜想。进一步的，我们猜想对任意的正整数k（k≥3），存在色数为3的图，其极小Wiener指数定向中含有至少k长的有向路，并证明了k≤6的情况。
　　第三章研究一些特殊图类的极小Wiener指数定向问题，给出了几个基本结果，研究了两类双圈图的极小定向。
　　第四章讨论具有较大Randi(c)指数的图结构，确定了含悬挂点三圈图的Randi(c)指数上界，给出了三圈图的前六大Randi(c)指数，并刻画了相应的极图。
　　第五章研究harmonic指数的极值问题，确定了三圈图的前六大harmonic指数及相应极图。

目录

声明

摘要

主要符号表

第一章引言

1．1有向图Wiener指数的研究进展

1．2连通性指数的研究现状

1．3本文研究的主要问题和所取得的主要结果

第二章着色导出定向猜想

2．1着色导出定向猜想的提出

2．2着色导出定向猜想的反例

2．3着色导出定向猜想的弱化形式

第三章双圈图的极小Wiener指数定向

3．1极小Wiener指数定向的几个结果

3．2∞型双圈图的极小Wiener指数

3．3θ型双圈图的极小Wiener指数

第四章三圈图的Randi?指数

4．2含悬挂点三圈图的Randi?指数上界

第五章三圈图的harmonic指数

5．1 harmonic指数的研究现状

5．2三圈图的前六大harmonic指数

参考文献

攻读硕士学位期间所取得的研究成果

致谢