Movatterモバイル変換


[0]ホーム

URL:


Jump to content
WikipediaThe Free Encyclopedia
Search

Algebraic graph theory

From Wikipedia, the free encyclopedia
Branch of mathematics
A highly symmetrical graph, thePetersen graph, which isvertex-transitive,symmetric,distance-transitive, anddistance-regular. It hasdiameter 2. Itsautomorphism group has 120 elements, and is in fact thesymmetric groupS5{\displaystyle S_{5}}.

Algebraicgraph theory is a branch ofmathematics in whichalgebraic methods are applied to problems aboutgraphs. This is in contrast togeometric,combinatoric, oralgorithmic approaches. There are three main branches of algebraic graph theory, involving the use oflinear algebra, the use ofgroup theory, and the study ofgraph invariants.

Branches of algebraic graph theory

[edit]

Using linear algebra

[edit]

The first branch of algebraic graph theory involves the study of graphs in connection withlinear algebra. Especially, it studies thespectrum of theadjacency matrix, or theLaplacian matrix of a graph (this part of algebraic graph theory is also calledspectral graph theory). For thePetersen 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 othergraph properties. As a simple example, aconnected graph withdiameterD will have at leastD+1 distinct values in its spectrum.[1]Aspects of graph spectra have been used in analysing thesynchronizability ofnetworks.

Using group theory

[edit]
Graph families defined by their automorphisms
distance-transitivedistance-regularstrongly regular
symmetric (arc-transitive)t-transitive,t ≥ 2skew-symmetric
(if connected)
vertex- and edge-transitive
edge-transitive and regularedge-transitive
vertex-transitiveregular(if bipartite)
biregular
Cayley graphzero-symmetricasymmetric

The second branch of algebraic graph theory involves the study of graphs in connection togroup theory, particularlyautomorphism groups andgeometric group theory. The focus is placed on various families of graphs based onsymmetry (such assymmetric graphs,vertex-transitive graphs,edge-transitive graphs,distance-transitive graphs,distance-regular graphs, andstrongly regular graphs), and on the inclusion relationships between these families. Certain of such categories of graphs are sparse enough thatlists of graphs can be drawn up. ByFrucht's theorem, allgroups can be represented as the automorphism group of a connected graph (indeed, of acubic graph).[2] Another connection with group theory is that, given any group, symmetrical graphs known asCayley graphs can be generated, and these have properties related to the structure of the group.[1]

ACayley graph for thealternating groupA4, forming atruncated tetrahedron in three dimensions. All Cayley graphs arevertex-transitive, but some vertex-transitive graphs (like thePetersen graph) are not Cayley graphs.
A proper vertex coloring of thePetersen graph with 3 colors, the minimum number possible. According to thechromatic 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 itsirreducible characters.[1][3]

Studying graph invariants

[edit]

Finally, the third branch of algebraic graph theory concerns algebraic properties ofinvariants of graphs, and especially thechromatic polynomial, theTutte polynomial andknot invariants. The chromatic polynomial of a graph, for example, counts the number of its propervertex colorings. For the Petersen graph, this polynomial ist(t1)(t2)(t712t6+67t5230t4+529t3814t2+775t352){\displaystyle t(t-1)(t-2)(t^{7}-12t^{6}+67t^{5}-230t^{4}+529t^{3}-814t^{2}+775t-352)}.[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 thefour color theorem. However, there are still manyopen problems, such as characterizing graphs which have the same chromatic polynomial, and determining which polynomials are chromatic.

See also

[edit]

References

[edit]
  1. ^abcdeBiggs, Norman (1993),Algebraic Graph Theory (2nd ed.), Cambridge University Press,ISBN 0-521-45897-8,Zbl 0797.05032
  2. ^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
  3. ^*Babai, L (1996),"Automorphism groups, isomorphism, reconstruction", in Graham, R;Grötschel, M; Lovász, L (eds.),Handbook of Combinatorics, Elsevier, pp. 1447–1540,ISBN 0-444-82351-4,Zbl 0846.05042, archived fromthe original on 2010-06-11, retrieved2009-03-27

External links

[edit]
Authority control databases: NationalEdit this at Wikidata
Retrieved from "https://en.wikipedia.org/w/index.php?title=Algebraic_graph_theory&oldid=1275510088"
Category:
Hidden categories:

[8]ページ先頭

©2009-2025 Movatter.jp