Introduction to Graph Theory and Algebraic Graph Theory
Graph theory is a branch of mathematics started by Euler [1] as early as 1736. It took a hundred years before the second important contribution of Kirchhoff [2] had been made for the analysis of electrical networks. Cayley [3] and Sylvester [4] discovered
- PDF / 1,260,300 Bytes
- 21 Pages / 439.37 x 666.142 pts Page_size
- 28 Downloads / 393 Views
Introduction to Graph Theory and Algebraic Graph Theory
2.1
Introduction
Graph theory is a branch of mathematics started by Euler [1] as early as 1736. It took a hundred years before the second important contribution of Kirchhoff [2] had been made for the analysis of electrical networks. Cayley [3] and Sylvester [4] discovered several properties of special types of graphs known as trees. Poincare´ [5] defined in principle what is known nowadays as the incidence matrix of a graph. It took another century before the first book was published by Ko¨nig [6]. After the Second World War, further books appeared on graph theory (Ore [7], Behzad and Chartrand [8], Tutte [9], Berge [10], Harary [11], Gould [12], Wilson [13], Wilson and Watkins [14] and West [15], among many others). Algebraic graph theory can be viewed as an extension to graph theory in which algebraic methods are applied to problems about graphs (Biggs [16]). Spectral graph theory, as the main branch of algebraic graph theory, is the study of properties of graphs in relationship to the characteristic polynomial, eigenvalues and eigenvectors of matrices associated with graphs, such as its adjacency matrix or Laplacian matrix. Spectral graph theory emerged in the 1950s and 1960s. The 1980 monograph Spectra of Graphs [17] by Cvetkovic´, Doob and Sachs has summarised nearly all research to date in the area. In 1988 it was updated by the survey Recent Results in the Theory of Graph Spectra [18]. Graph theory has found many applications in engineering and science, such as chemical, electrical, civil and mechanical engineering, architecture, management and control, communication, operational research, sparse matrix technology, combinatorial optimisation and computer science. Therefore, many books have been published on applied graph theory such as those by Bondy and Murty [19], Chen [20], Thulasiraman and Swamy [21], Beineke and Wilson [22], Mayeda [23], Christofides [24], Gondran and Minoux [25], Deo [26], Cooke et al. [27] and Kaveh [28, 29]. In recent years, due to the extension of the concepts and applications of the graph theory, many journals such as Journal of Graph Theory, Journal of Combinatorial Theory A & B, Discrete and Applied Mathematics, SIAM A. Kaveh, Optimal Analysis of Structures by Concepts of Symmetry and Regularity, DOI 10.1007/978-3-7091-1565-7_2, © Springer-Verlag Wien 2013
15
16
2 Introduction to Graph Theory and Algebraic Graph Theory
Journal of Discrete Mathematics, European Journal of Combinatorics and Graphs and Combinatorics are being published to cover the advances made in this field. In this chapter basic definitions and concepts of graph theory and algebraic graph theory are briefly presented; however, for proofs and details the reader may refer to textbooks on this subject, Refs. [11, 15, 28, 29].
2.2
Basic Concepts and Definitions of Graph Theory
There are many physical systems whose performance depends not only on the characteristics of their components but also on their relative location. As an example, in a structure,
Data Loading...
