Graph Theory| 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