Graph Theory |

**In General** > s.a. graph theory in physics;
networks; types of graphs.

$ __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)
[pdf].

main page
– abbreviations
– journals – comments
– other sites – acknowledgements

send feedback and suggestions to bombelli at olemiss.edu – modified 3 jun 2019