The first branch of algebraic graph theory involves the study of graphs in connection with linear algebra. Especially, it studies the spectrum of the adjacency matrix, or the Laplacian matrix of a graph (this part of algebraic graph theory is also called spectral graph theory). For the Petersen graph, for example, the spectrum of the adjacency matrix is (−2, −2, −2, −2, 1, 1, 1, 1, 1, 3). Several theorems relate properties of the spectrum to other graph properties. As a simple example, a connected graph with diameterD will have at least D+1 distinct values in its spectrum.[1]Aspects of graph spectra have been used in analysing the synchronizability of networks.
This second branch of algebraic graph theory is related to the first, since the symmetry properties of a graph are reflected in its spectrum. In particular, the spectrum of a highly symmetrical graph, such as the Petersen graph, has few distinct values[1] (the Petersen graph has 3, which is the minimum possible, given its diameter). For Cayley graphs, the spectrum can be related directly to the structure of the group, in particular to its irreducible characters.[1][3]
Studying graph invariantsedit
Finally, the third branch of algebraic graph theory concerns algebraic properties of invariants of graphs, and especially the chromatic polynomial, the Tutte polynomial and knot invariants. The chromatic polynomial of a graph, for example, counts the number of its proper vertex colorings. For the Petersen graph, this polynomial is .[1] In particular, this means that the Petersen graph cannot be properly colored with one or two colors, but can be colored in 120 different ways with 3 colors. Much work in this area of algebraic graph theory was motivated by attempts to prove the four color theorem. However, there are still many open problems, such as characterizing graphs which have the same chromatic polynomial, and determining which polynomials are chromatic.
^ abcdeBiggs, Norman (1993), Algebraic Graph Theory (2nd ed.), Cambridge University Press, ISBN0-521-45897-8, Zbl 0797.05032
^Frucht, R. (1949), "Graphs of Degree 3 with given abstract group", Can. J. Math., 1 (4): 365–378, doi:10.4153/CJM-1949-033-6
^*Babai, L (1996), , in Graham, R; Grötschel, M; Lovász, L (eds.), Handbook of Combinatorics, Elsevier, pp. 1447–1540, ISBN0-444-82351-4, Zbl 0846.05042, archived from the original on 2010-06-11, retrieved 2009-03-27
Media related to Algebraic graph theory at Wikimedia Commons
January 01, 1970
algebraic, graph, theory, branch, mathematics, which, algebraic, methods, applied, problems, about, graphs, this, contrast, geometric, combinatoric, algorithmic, approaches, there, three, main, branches, algebraic, graph, theory, involving, linear, algebra, gr. Algebraic graph theory is a branch of mathematics in which algebraic methods are applied to problems about graphs This is in contrast to geometric combinatoric or algorithmic approaches There are three main branches of algebraic graph theory involving the use of linear algebra the use of group theory and the study of graph invariants A highly symmetrical graph the Petersen graph which is vertex transitive symmetric distance transitive and distance regular It has diameter 2 Its automorphism group has 120 elements and is in fact the symmetric group S 5 displaystyle S 5 Contents 1 Branches of algebraic graph theory 1 1 Using linear algebra 1 2 Using group theory 1 3 Studying graph invariants 2 See also 3 References 4 External linksBranches of algebraic graph theory editUsing linear algebra edit The first branch of algebraic graph theory involves the study of graphs in connection with linear algebra Especially it studies the spectrum of the adjacency matrix or the Laplacian matrix of a graph this part of algebraic graph theory is also called spectral graph theory For the Petersen graph for example the spectrum of the adjacency matrix is 2 2 2 2 1 1 1 1 1 3 Several theorems relate properties of the spectrum to other graph properties As a simple example a connected graph with diameter D will have at least D 1 distinct values in its spectrum 1 Aspects of graph spectra have been used in analysing the synchronizability of networks Using group theory edit Graph families defined by their automorphisms distance transitive distance regular strongly regular symmetric arc transitive t transitive t 2 skew symmetric if connected vertex and edge transitive edge transitive and regular edge transitive vertex transitive regular if bipartite biregular Cayley graph zero symmetric asymmetric The second branch of algebraic graph theory involves the study of graphs in connection to group theory particularly automorphism groups and geometric group theory The focus is placed on various families of graphs based on symmetry such as symmetric graphs vertex transitive graphs edge transitive graphs distance transitive graphs distance regular graphs and strongly regular graphs and on the inclusion relationships between these families Certain of such categories of graphs are sparse enough that lists of graphs can be drawn up By Frucht s theorem all groups can be represented as the automorphism group of a connected graph indeed of a cubic graph 2 Another connection with group theory is that given any group symmetrical graphs known as Cayley graphs can be generated and these have properties related to the structure of the group 1 nbsp A Cayley graph for the alternating group A4 forming a truncated tetrahedron in three dimensions All Cayley graphs are vertex transitive but some vertex transitive graphs like the Petersen graph are not Cayley graphs nbsp A proper vertex coloring of the Petersen graph with 3 colors the minimum number possible According to the chromatic polynomial there are 120 such colorings with 3 colors This second branch of algebraic graph theory is related to the first since the symmetry properties of a graph are reflected in its spectrum In particular the spectrum of a highly symmetrical graph such as the Petersen graph has few distinct values 1 the Petersen graph has 3 which is the minimum possible given its diameter For Cayley graphs the spectrum can be related directly to the structure of the group in particular to its irreducible characters 1 3 Studying graph invariants edit Finally the third branch of algebraic graph theory concerns algebraic properties of invariants of graphs and especially the chromatic polynomial the Tutte polynomial and knot invariants The chromatic polynomial of a graph for example counts the number of its proper vertex colorings For the Petersen graph this polynomial is t t 1 t 2 t 7 12 t 6 67 t 5 230 t 4 529 t 3 814 t 2 775 t 352 displaystyle t t 1 t 2 t 7 12t 6 67t 5 230t 4 529t 3 814t 2 775t 352 nbsp 1 In particular this means that the Petersen graph cannot be properly colored with one or two colors but can be colored in 120 different ways with 3 colors Much work in this area of algebraic graph theory was motivated by attempts to prove the four color theorem However there are still many open problems such as characterizing graphs which have the same chromatic polynomial and determining which polynomials are chromatic See also editSpectral graph theory Algebraic combinatorics Algebraic connectivity Dulmage Mendelsohn decomposition Graph property Adjacency matrixReferences edit a b c d e Biggs Norman 1993 Algebraic Graph Theory 2nd ed Cambridge University Press ISBN 0 521 45897 8 Zbl 0797 05032 Frucht R 1949 Graphs of Degree 3 with given abstract group Can J Math 1 4 365 378 doi 10 4153 CJM 1949 033 6 Babai L 1996 Automorphism groups isomorphism reconstruction in Graham R Grotschel M Lovasz L eds Handbook of Combinatorics Elsevier pp 1447 1540 ISBN 0 444 82351 4 Zbl 0846 05042 archived from the original on 2010 06 11 retrieved 2009 03 27 Godsil Chris Royle Gordon 2001 Algebraic Graph Theory Graduate Texts in Mathematics vol 207 Springer ISBN 0 387 95220 9 Zbl 0968 05002 External links edit nbsp Media related to Algebraic graph theory at Wikimedia Commons Retrieved from https en wikipedia org w index php title Algebraic graph theory amp oldid 1187125276, wikipedia, wiki, book, books, library,
