Graph Theory

In General > s.a. networks.
$ Graph: A network containing no multiple edges.
* Applications: Graphs can be used to represent relations on a set.

Related Concepts > s.a. Cycle; graph invariants; graph types; statistical geometry.
* Hamiltonian cycle: A closed path that visits every vertex once and only once.
* 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.
@ Hamiltonian cycles: Higuchi MPLA(98) [counting, planar].
@ Minors: Robertson & Seymour JCTB(04); Lovász BAMS(06).
@ Operations: Ryjácek JCTB(97), Kelmans DM(03) [closure]; Saito JCTB(03) [splitting in 4-connected graphs]; Audenaert et al JCTB(07) [symmetric squares].
@ Related topics: Kostochka & Tashkinov Ord(03) [decomposition into long paths]; Fan JCTB(05) [Gallai's conjecture].

Topology on a Graph > s.a. cell complex.
* Weakly compatible topology: A topology on { · } is compatible with the graph G = ({ · }, { ↑ }) if for every finite subgraph A G, A is connected iff it is topologically connected.
* Compatible topology: A topology on { · } is compatible with the graph G = ({ · }, { ↑ }) if for every subgraph A G, A is connected iff it is topologically connected.
* Result: A weakly compatible topology on { · } determines the graph uniquely.
@ References: Neumann-Lara & Wilson Ord(95) [compatibility].

Other Structures on Graphs > s.a. euclidean geometry [polyhedra]; graph functions.
* Distance: The path metric on graphs is defined as d(x, y):= min{l(p) | paths p connecting x and y}.
* 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].
@ Hilbert space decoration: Requardt JPA(02)mp/01 [and operators].
@ Distance: in Chang et al EJC(04) [geodetic]; Cáceres et al EJC(08) [Steiner, and convexity]; > s.a. types of graphs
@ 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].

References > s.a. graph theory in physics.
@ General: Harary 69; Bundy & Murty 76; Bollobás 79; Cvetkovic et al 80; Aigner 84; Berge 85; Bollobás 98; Gross & Yellen 03 [handbook].
@ Special emphasis: Clark & Holton 91 [applications]; Gross 01 [topological]; Golumbic 03 [algorithmic]; Pemmaraju & Skiena 03 [numerical]; Bollobás 04 [extremal graph theory]; Zemanian 04 [transfinite].
@ Isomorphism problem: Gudkov et al cm/02, Gudkov & Nussinov cm/02; Shiau et al QIC(05)qp/03 [and many-particle computation]; > s.a. random process [quantum random walk].
@ Counting, enumeration: Pittel & Wormald JCTB(05) ["inside-out"].
@ Related topics: Voss 91 [cycles, bridges]; Chung & Graham 97 [update]; Collet & Eckmann mp/02 [density of triangles]; Buckley & Osthus DM(04) [random growth model]; Kim & Wilhelm PhyA(08) [complexity].
@ Applications: Erdös et al DM(72);

Web Resources > see www.graphtheory.com.

Main page – Abbreviations – Journals – Comments – Other sites – Acknowledgements
Send feedback and suggestions to bombelli at olemiss.edu – Modified 13 mar 2008