Graph Theory  

In General > s.a. graph theory in physics; networks.
$ Def: A graph is a network containing no multiple edges.
* Applications: Graphs can be used to represent relations on a set.
@ General references: Harary 69; Bollobás 79; Aigner 84; Berge 85; Bollobás 98; Gross & Yellen 05; Bondy & Murty 08; Xiong & Zheng 10 [II]; in Vermani & Vermani 12 [discrete mathematics].
@ Special emphasis: Cvetković et al 80 [spectra]; Clark & Holton 91 [applications]; Gross 01, Gross & Tucker 12 [topological]; Golumbic 03 [algorithmic]; Gross & Yellen ed-03 [handbook]; Pemmaraju & Skiena 03 [numerical]; Bollobás 04 [extremal graph theory]; Zemanian 04 [transfinite].
@ Applications: Erdős et al DM(72).

Other Structures on Graphs > s.a. graph invariants [adjacency, topology]; Gauss-Bonnet Operator and laplacian.
* Neighborhood complex: The simplicial complex having all subsets of vertices with a common neighbor in the graph as its faces.
@ Ranking: van den Brink & Gilles DM(03).
@ Colorings: Balister et al JCTB(04) [balanced]; Barbosa & Ferreira PhyA(04) [phase transitions]; Balogh EJC(06) [number]; Kramer & Kramer DM(08) [distance colorings, survey].
@ Operators: Requardt JPA(02)mp/01 [Dirac operator, Hilbert space]; Schott & Staples 12 [Clifford-algebra framework].
@ Related topics: Kastler JMP(04) [exterior structure]; Cáceres et al DM(05) [convex subsets]; Heggernes DM(06) [minimal triangulations]; van der Holst JCTB(06) [2D CW-complexes and 4-manifolds]; Kahle JCTA(07) [neighborhood complex of a random graph]; Espinosa a0905 [Matsubara sums]; Morgan DM(09) [dynamic adjacency labelling scheme]; Trinchero a1004-proc [quantum grupoid from space of paths].
> Related topics: see euclidean geometry [polyhedra]; subsets and operations on graphs [including distance/metric and geometrical concepts].

Results, Conjectures and Related Topics > s.a. graph invariants [Hadwiger conjecture].
* Isomorphism problem: It is neither known to be in P nor known to be NP-complete, although most theoretical computer scientists believe that it is not NP-complete, among other reasons because there is a blind-taste-test protocol for it; Babai's 2015 proposed algorithm brings it close to being in P.
* Gallai's conjecture: If G is a connected simple graph on n vertices, the edges of G can be decomposed into [n/2] paths.
* Wagner's conjecture: For any infinite set of graphs, one is isomorphic to a minor of another.
@ Isomorphism problem: Gudkov et al cm/02; Gudkov & Nussinov cm/02; Shiau et al QIC(05)qp/03 [and many-particle computation]; Babai a1512 + news sn(15)nov, Quanta(15)dec, sn(17)jan [quasipolynomial time algorithm]; Mills et al a1711 [proposal for an efficient quantum algorithm]; > s.a. random process [quantum random walk].
@ Counting, enumeration: Pittel & Wormald JCTB(05) ["inside-out"].
@ Related topics: Voss 91 [cycles, bridges]; Chung & Graham 98 [update on Erdős problems]; Collet & Eckmann mp/02 [density of triangles]; Buckley & Osthus DM(04) [random growth model]; Fan JCTB(05) [Gallai's conjecture]; Kim & Wilhelm PhyA(08) [complexity]; Akiyama & Kano 11 [factors and factorizations]; Grady & Polimeni 10 [discrete calculus].

* Classical representation: A realization of a graph as a set of vertices and connecting straight edges in Euclidean space, such that distinct vertices are distinct points and all edges have unit length, but distinct edges may intersect.
* Geometric graph: A graph in which the vertices or edges are associated with geometric objects or configurations (for example, a graph embedded in a manifold); > s.a. Wikipedia page.
* Algebraic formulation: Any graph can be represented as an adjacency matrix, or in terms of properties of the algebra of functions over the set of vertices and edges.

Online Resources > see Wikipedia page;

Generalizations of Graphs > s.a. graphs in physics [quantum graphs].
$ Hypergraph: A pair (X, A), with X a non-empty set, A a covering of X; > s.a. quantum states [hypergraph states].
* Graphons: (Short for graph function) Objects introduced in 2006 by Lovász and Szegedy as limits of sequences of large, finite graphs with respect to the so-called cut metric; Graphs are special types of graphons.
@ References: Berge 73, 89 [hypergraphs]; Filk IJTP(00) [non-commutative graph, distance function].
@ Graphons: Lovász 12; Glassock talk(13); Wolfe & Olhede a1309; Glassock NAMS(15).

main pageabbreviationsjournalscommentsother sitesacknowledgements
send feedback and suggestions to bombelli at – modified 27 nov 2017