具有相同路径层矩阵不同构的r-正则图

摘要

图论是应用数学理论的重要分支.图论的广泛应用,促进了它自身的发展.尤其是近几十年来,随着计算机技术的出现和进步,图论理论有了飞速的发展并取得了惊人的成绩.该文所研究的具有相同路径层矩阵不同构的图的问题是在药品分析的实际应用领域中提出来的.一个图G的路径层矩阵τ(G)(the path layer matrix)包含关于图G中的所有路径的定量信息.矩阵元素τi,j表示图G中起点为i,路径长度为j的路径数.图的路径层矩阵与图的同构问题密切相关.记f(r)为具有相同路径层矩阵的不同构的r-正则图的最少顶点数.求解任意r-正则图的f(r)是一件非常有意义且很有难度的工作.1990年,Dobrynin构造出了一系列具有相同路径层矩阵不同构的正则图,证明了对于任意r≥3,存在具有相同路径层矩阵的不同构的r-正则图(A.A.Dobrynin.Regular graphs having the same path layer matrix.J GraphTheory,1990,14:141-148).在这篇论文中,Dobrynin给出的上界结果是f(r)≤18r+36 (r=2m,m≥3),f(r)≤20r+48(r=4m+3,m≥1),f(r)≤20r+64(r=4m+5,m≥0).2002年,杨元生等将结果改进到f(5)≤48,f(6)≤51(杨元生,林建华,王春立.Small reguhlargraphs having the same path layer matrix.J Graph Theory,2002,39:2l 9-221).在该文之前,没有人能够给出具有相同路径层矩阵不同构的任意r-正则图的更好的统一构造方法,r为任意值时的f(r)的上界也没有得到改进.该文对路径层矩阵相关问题进行了深入研究,设计出了新的构图方案,利用3-相似图的性质,结合类似于完全二部图的连接方式,成功地构造出了一系列具有相同路径层矩阵但不同构的r-正则图,并给出了其正确性的完整数学证明.该文将f(r)的上界降至f(r)≤2r+20(r=3,5),f(r)≤5r+11(r=6,8,10),f(r)≤2r+8(r=7,9或r≥11),从而极大地改善了原有的结果.该文已投往SCI刊源杂志Graphs and Combinatorics.

目录

文摘

英文文摘

前言

1路径层矩阵相关概念

2路径层矩阵的进展

2.1路径层矩阵

2.2具有相同路径层矩阵不同构的图对

2.3具有相同路径层矩阵不同构的正则图的早期数学方法构造

2.4具有相同路径层矩阵不同构的小正则图的构造

2.5具有相同路径层矩阵不同构的无割点的图

2.6具有相同路径层矩阵不同构的无割点的4-正则图

2.7本文的工作

3具有相同路径层矩阵不同构的图对的构造方法

3.1直接搜索法

3.2含割点的具有相同路径层矩阵不同构的图对的数学构造方法

3.3不含割点的具有相同路径层矩阵不同构图对的数学构造方法

3.3.1两点连接构成具有相同路径层矩阵不同构的图对

3.3.2三点连接构成具有相同路径层矩阵不同构的图对

4用3-相似图构造具有相同路径层矩阵不同构的r-正则图

4.1 3-相似图举例

4.2用3-相似图构造具有相同路径层矩阵不同构的图对的示例

4.3用3-相似图和任意图拼接构造具有相同路径层矩阵但不同构的r-正则图

5成果与展望

参考文献

致谢

大连理工大学学位论文版权使用授权书