I first read this book during one of my master degree classes. That's why it was difficult for me to understand some of the concepts and methods when reading it the first time. I came to this book from time to time when needed, but last year I started to teach MA Algebraic Graph Theory which gave me an opportunity to give a closer look.
Overall, it is a g I first read this book during one of my master degree classes. Overall, it is a good book for graduate students. It gives all the necessary backgrounds and important facts on three big ideas: linear algebra in Graph Theory, coloring problems, symmetry and regularity. It gives mostly sketches of proofs, which give students opportunities to think and have a deeper look into some of the theorems.
This book is a classic and so it lacks of some of the new results connected to the field. Godsil and Royle's book with the same title, for instance, gives a more cutting-edge applications. Shyama Manikandan rated it it was amazing May 06, Felix rated it it was amazing Mar 04, Aswini Kumar rated it it was amazing Jul 23, Mitch rated it liked it Nov 20, William Hopkins rated it it was amazing Apr 01, Asad Turan rated it it was amazing Jun 07, Jernej rated it it was amazing Apr 17, Alice rated it really liked it Jul 31, Subhas Ghosh rated it really liked it Jan 15, David Leach rated it it was amazing Jan 20, Alon Friedman rated it liked it Nov 07, Martin Cohen marked it as to-read Dec 16, Arinta added it Jun 01, Jj marked it as to-read Oct 13, Bahram marked it as to-read Nov 15, Sarah added it Sep 15, Wamg marked it as to-read Feb 23, Prem Prasanna added it Jul 14, Suma Latha marked it as to-read Dec 03, Yeva Fadhilah marked it as to-read Apr 05, Kenny Thomas added it Aug 09, Arindam Das marked it as to-read Aug 22, Chithu marked it as to-read Jan 10, Majid marked it as to-read Jan 01, Jairo marked it as to-read Mar 15, Anna Melikyan marked it as to-read Apr 12, Arash Ashrafzadeh marked it as to-read Jun 09, Shohreh marked it as to-read Jun 10, Randa marked it as to-read Aug 17, BookDB marked it as to-read Oct 27, Matt marked it as to-read Jun 02, There are no discussion topics on this book yet.
Be the first to start one ». About Norman Biggs. Norman Biggs. Other books in the series. Cambridge Mathematical Library 1 - 10 of 29 books. I should venture the opinion that , were it not for his pioneering work, these results would still be unknown to this day.
This book is concerned with the use of algebraic techniques in the study of graphs. We aim to translate properties of graphs into algebraic properties and then, using the results and methods of algebra, to deduce theorems about graphs.
The exposition which we shall give is not part of the modern functorial approach to topology, despite the claims of those who hold that, since graphs are one-dimensional spaces, graph theory is merely one-dimensional topology. By that definition, algebraic graph theory would consist only of the homology of 1-complexes. But the problems dealt with in graph theory are more delicate than those which form the substance of algebraic topology, and even if these problems can be generalized to dimensions greater than one, there is usually no hope of a general solution at the present time.
Consequently, the algebra used in algebraic graph theory is largely unrelated to the subject which has come to be known as homological algebra.
This book is not an introduction to graph theory. I t would be to the reader's advantage if he were familiar with the basic concepts of the subject, for example, as they are set out in the book by R.
Wilson entitled Introduction to graph theory. However, for the convenience of those readers who do not have this background, we give brief explanations of important standard terms.
These explanations are usually accompanied by a reference to Wilson's book in the form [W, p. In the same way, some concepts from permutation-group theory are accompanied by a reference [B, p.
Both these books are described fully at the end of this chapter. A few other books are also referred to for results which may be unfamiliar to some readers. In such cases, the result required is necessary for an understanding of the topic under discussion, so that the reference is given in full, enclosed in square brackets,. Other references, of a supplementary nature, are given in parentheses in the form Smith or Smith In such cases, the full reference may be found in the bibliography at the end of the book.
The tract is in three parts, each of which is further subdivided into a number of short chapters. Within each chapter, the major definitions and results are labelled using the decimal system. The first part deals with the applications of linear algebra and matrix theory to the study of graphs. We begin by introducing the adjacency matrix of a graph; this matrix completely determines the graph, and its spectral properties are shown to be related to properties of the graph.
For example, if a graph is regular, then the eigenvalues of its adjacency matrix are bounded in absolute value by the valency of the graph. In the case of a line graph, there is a strong lower bound for the eigenvalues. Another matrix which completely describes a graph is the incidence matrix of the graph.
This matrix represents a linear mapping which, in modern language, determines the homology of the graph; however, the sophistication of this language obscures the underlying simplicity of the situation.
The problem of choosing a basis for the homology of a graph is just that of finding a fundamental system of circuits, and we solve this problem by using a spanning tree in the graph. At the same time we study the cutsets of the graph. These ideas are then applied to the systematic solution of network equations, a topic which supplied the stimulus for the original theoretical development.
We then investigate various formulae for the number of spanning trees in a graph, and apply these formulae to several well-known families of graphs. The first part of the book ends with results which are derived from the expansion of certain determinants, and which illuminate the relationship between a graph and the characteristic polynomial of its adjacency matrix. The second part of the book deals with the problem of colouring the vertices of a graph in such a way that adjacent vertices have different colours.
The least number of colours for which such a colouring is possible is called the chromatic number of the graph, and we begin by investigating some connections between this. The algebraic technique for counting the colourings of a graph is founded on a polynomial known as the chromatic polynomial. We first discuss some simple ways of calculating this polynomial, and show how these can be applied in several important cases. Many important properties of the chromatic polynomial of a graph stem from its connection with the family of subgraphs of the graph, and we show how the chromatic polynomial can be expanded in terms of subgraphs.
From our first additive expansion another multiplicative expansion can be derived, and the latter depends upon a very restricted class of subgraphs. This leads to efficient methods for approximating the chromatic polynomials of large graphs.
A completely different kind of expansion relates the chromatic polynomial to the spanning trees of a graph; this expansion has several remarkable features and leads to new ways of looking at the colouring problem, and some new properties of chromatic polynomials.
The third part of the book is concerned with symmetry and regularity properties. A symmetry property of a graph is related to the existence of automorphisms-that is, permutations of the vertices which preserve adjacency.
A regularity property is defined in purely numerical terms. Consequently, symmetry properties induce regularity properties, but the converse is not necessarily true. We first study the elementary properties of automorphisms, and explain the connection between the automorphisms of a graph and the eigenvalues of its adjacency matrix.
0コメント