algebraic graph theory

aesthetics  →
being  →
complexity  →
database  →
enterprise  →
ethics  →
fiction  →
history  →
internet  →
knowledge  →
language  →
licensing  →
linux  →
logic  →
method  →
news  →
perception  →
philosophy  →
policy  →
purpose  →
religion  →
science  →
sociology  →
software  →
truth  →
unix  →
wiki  →
essay  →
feed  →
help  →
system  →
wiki  →
critical  →
discussion  →
forked  →
imported  →
original  →
algebraic graph theory
[ temporary import ]
please note:
- the content below is remote from Wikipedia
- it has been imported raw for GetWiki
missing image!
- Petersen1 tiny.svg|thumb|200px|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 groupsymmetric groupAlgebraic 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.

Branches of algebraic graph theory

Using linear algebra

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.{{Citation | author=Biggs, Norman | title=Algebraic Graph Theory | edition=2nd | location=Cambridge | publisher=Cambridge University Press | year=1993 | isbn=0-521-45897-8 | postscript=}} Aspects of graph spectra have been used in analysing the synchronizability of networks.

Using group theory

{{Graph families defined by their automorphisms}}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).R. Frucht. Graphs of Degree 3 with given abstract group, Can. J. Math. 3 1949. 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.TruncatedTetrahedron.gif
Image:Petersen graph 3-coloring.svg|thumb|right|200px|A proper vertex coloring of the Petersen graph with 3 colors, the minimum number possible. According to the chromatic polynomialchromatic polynomialThis 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 (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.*{{Citation | first = L | last = Babai | editor-last = Graham | editor-first = R | editor2-last = Grötschel | editor2-first = M | editor2-link = Martin Grötschel | editor3-last = Lovász | editor3-first = L | title = Handbook of Combinatorics | contribution = Automorphism groups, isomorphism, reconstruction | contribution-url =weblink | year = 1996 | publisher = Elsevier | postscript = }}

Studying graph invariants

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-12t^6+67t^5-230t^4+529t^3-814t^2+775t-352). 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


  • {{citation|first1=Chris|last1=Godsil|authorlink1=Chris Godsil|first2=Gordon|last2=Royle|authorlink2=Gordon Royle|title=Algebraic Graph Theory|series=Graduate Texts in Mathematics|volume=207|publisher=Springer-Verlag|location=New York|year=2001|postscript=}}.

External links

- content above as imported from Wikipedia
- "algebraic graph theory" does not exist on GetWiki (yet)
- time: 10:44pm EDT - Mon, Sep 16 2019
[ this remote article is provided by Wikipedia ]
LATEST EDITS [ see all ]
Eastern Philosophy
History of Philosophy
M.R.M. Parrott