定义

最新进展

推荐书籍

定义

代数图论是数学中离散数学的一个分支，主要是应用代数方法解决图论问题，而不是几何、组合或算术方法。其主要有三个分支，分别是线性代数方法、群论方法和图不变量方法。

最新进展

图的minor理论是近代图论研究的中心问题之一。在我国很少有这方面的研究成果。国际上, 洪渊等人首先研究了图的minor与图的特征值之间的关系。其中，图的树宽度又是图的minor理论中的一个重要参数。他们给出了树宽度不大于k的所有图其谱半径的可达上界和达到上界的极图。同时对树宽度不大于k的所有图得到最小特征值的可达上界和达到上界的极图。另外，对于禁用K5–minor图给出了其谱半径的可达上界和达到上界的极图。同时对禁用K5–minor图得到了其最小特征值的可达下界和达到下界的极图。而对于t=n，n-1，n-2的禁用Kt–minor图给出了其谱半径的可达上界和达到上界的极图。

在研究了谱图理论及应用方面，张晓东和李炯生讨论了混合图的性质和图的拉普拉斯的矩阵的最大特征值的上界的估计，并刻画了达到上界的所有的图类。他们把图的拉普拉斯矩阵的研究推广到新的领域。在完全正则图的分解指数方向，解决了Berman和Kogan的关于完全正则图的问题。整图是指该图的Laplace特征值或邻接特征值都是整数；这类图的拓扑结构和它们的特征值存在着一些有趣的联系。远在1970年代，Harary和Schwenk提出研究整图的问题。但至今，这个问题仍没有完全解决。范益政和李炯生提出了新概念谱整性变化。谱整性变化是图的谱扰动的一种情形。它的提出为了解图的谱扰动，特别是构造整图提供了新的方法和视角。此后，他们用这种方法还讨论了度极大图，具有少数匹配数的树，以及混合图的谱扰动。另外，李炯生等人研究了经典Turan数t(Kr,r,n)在可图序列中的变形,确定了t(Kr,r,n)的度序列形式的极值å(Kr,r,n)，为研究极值图论的经典结果在可图序列中的变形问题提供了一个范例和研究方法。

张福基等人研究了谱半径小于 ormulas> eqn="if lineDrawn pixelLineWidth 0">> eqn="sum @0 1 0">>le="" type="#_x0000_t75">(图谱半径在实轴上的最小聚点)的连通图依谱半径大小的排序。他们首次引进了渐近序的概念，证明了所考虑的图类只存在渐进序。同时解决了一个无穷图类依谱半径排序的问题。他们还进而还考虑了上述结果在化学中的应用。另外，洪渊等人研究了如何用图的度序列确定图的Laplace谱半径的可达上界和达到上界的极图。

方新贵、王杰和徐明耀对于有限单群Cayley图的全自同构群的结构给予了刻画，证明了图的全自同构群或是几乎单的或有着极强的限制性结构。作为一个应用，他们还得到了一个有限单群Cayley图正规性的充分条件，并由此构造出了若干新的半传递图，其中两个图的无限族具有任意大的度数。另外他们还得到一个充分条件以使的有限非交换单群的Cayley图是弧正则的。据此他们构造了两个3度弧正则图的无限族使其全自同构群是非可解的，且其中一个无限族不是Cayley图。同时他们还证明了对大多数有限非交换单群决定的3度Cayley图均是正规的，并将此结果应用于群的图正则表示和3-CI性的刻画

推荐书籍

书名:代数图论图书编号:1014024

出版社:世界图书出版公司

定价:65.0

ISBN:750626618

作者:Chris Godsil

出版日期:2004-04-01

版次:1

开本:横24开

简介:本书以英文的形式介绍了代数图论的有关内容。

目录:Preface

1 Graphs

1.1 Graphs

1.2 Subgraphs

1.3 Automorphisms

1.4 Homomorphisms

1.5 Circulant Graphs

1.6 Johnson Graphs

1.7 Line Graphs

1.8 Planar Graphs

Exercises

Notes

References

2 Groups

2.1 Permutation Groups

2.2 Counting

2.3 Asymmetric Graphs

2.4 Orbits on Pairs

2.5 Primitivity

2.6 Primitivity and Connectivity

Exercises

Notes

References

3 Transitive Graphs

4 Arc-Transitive Graphs

5 Generalized Polygons and Moore Graphs

6 Homomorphisms

7 Kneser Graphs

8 Matrix Theory

9 Interlacing

10 Strongly Regular Graphs

11 Two-Graphs

12 Line Graphs and Eigenvalues

13 The Laplacian of a Graph

14 Cuts and Flows

15 The Rank Polynomial

16 Konts

17 Knots and Eulerial Cycles

Glossary of Symbols

Index