Graphs and Matrices
Graphs and Matrices
复制标题
DOI：
10.1007/978-1-4471-6569-9
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
R. Bapat
中科院分区：
文献类型：
--
作者：
R. Bapat
这本书关注的结果在图论中，线性代数和矩阵理论发挥了重要作用。虽然人们普遍认为线性代数可以是图的研究中的一个重要组成部分，但传统上，图论家对使用线性代数的热情仍然很低。这里讨论的结果通常在代数图论中处理，正如Biggs [20]以及Godsil和Royle [39]的经典书籍中所概述的那样。我们对矩阵技术的强调甚至超过了这些，也许这里讨论的主题可以被称为线性代数图论来突出这一方面。1，接下来的几章概述了与图相关的一些矩阵的基本性质。其次是图论中的主题，如正则图和代数连通性。在接下来的两章中，我们讨论了树的距离矩阵及其对任意图的推广形式--阻力矩阵。最后一章处理其他主题，如阈值图的拉普拉斯特征值，正定完成问题，矩阵游戏的基础上的一个图。我们一直保持在一个相当初级的水平，并抵制诱惑，介绍了最新的研究工作。因此，本书中的几个章节可以被看作是对当前蓬勃发展的研究的一个广阔领域的邀请。这里只是一个开始，希望它能吸引读者进一步探索。同样，我们通常不会以其完整的一般性来呈现结果，而只是呈现一个简单的版本，以捕捉结果的优雅。加权图是避免的，虽然这里提出的大多数结果加权，因此更一般，类似物。
This book is concerned with results in graph theory in which linear algebra and matrix theory play an important role. Although it is generally accepted that linear algebra can be an important component in the study of graphs, traditionally, graph theorists have remained by and large less than enthusiastic about using linear algebra. The results discussed here are usually treated under algebraic graph theory, as outlined in the classic books by Biggs [20] and by Godsil and Royle [39]. Our emphasis on matrix techniques is even greater than what is found in these and perhaps the subject matter discussed here might be termed linear algebraic graph theory to highlight this aspect.After recalling some matrix preliminaries in the Chap. 1, the next few chapters outline the basic properties of some matrices associated with a graph. This is followed by topics in graph theory such as regular graphs and algebraic connectivity. Distance matrix of a tree and its generalized version for arbitrary graphs, the resistance matrix, are treated in the next two chapters. The final chapters treat other topics such as the Laplacian eigenvalues of threshold graphs, the positive definite completion problem, and matrix games based on a graph. We have kept the treatment at a fairly elementary level and resisted the temptation of presenting up-to-date research work. Thus, several chapters in this book may be viewed as an invitation to a vast area of vigorous current research. Only a beginning is made here with the hope that it will entice the reader to explore further. In the same vein, we often do not present the results in their full generality, but present only a simpler version that captures the elegance of the result. Weighted graphs are avoided, although most results presented here have weighted, and hence more general, analogs.