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].

**Representations**

* __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; www.graphtheory.com.

**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 page – abbreviations – journals – comments – other
sites – acknowledgements

send feedback and suggestions to bombelli at olemiss.edu – modified 27
nov 2017