Special Types of Graphs and Embeddings  

Main Types of Single Graphs > s.a. networks [scale-free]; Polymers; posets; Relations [k-homogeneous].
$ Directed: ("digraph") A set of objects { · } and arrows {↑}, with two maps

dom: {↑} → { · }   and   cod: {↑} → { · } .

$ Simple: A graph with no loops (a tree?).
$ Regular: A graph such that all vertices have the same 'degree' (valence); In a regular graph of valence v, the number of cycles of length L starting at a vertex is bounded by a polynomial of order v L–1.
$ Bipartite: Its vertices can be divided into classes/layers A, B, such that each edge has one vertex in A and one in B.
$ Complete: A graph in which every pair of vertices is connected by an edge.
$ Doubly connected: A connected graph whose complement is also connected.
$ Hamiltonian: A (connected) graph that has a Hamiltonian cycle, i.e., one that goes through every vertex exactly once.
* Planar: The set Pn of labelled planar graphs with n vertices satisfies n! (26.1)n+o(n) |Pn| n! (37.3)n+o(n), and almost all graphs in Pn have at least 13/7 n and at most 2.56 n edges.
* Spherical: A graph in which every interval is antipodal; Spherical graphs are an interesting generalization of hypercubes (a graph G is a hypercube if and only if G is spherical and bipartite).
* Chromatic-index-critical: A graph which cannot be edge-coloured with colours (with the maximal degree of the graph), and such that the removal of any edge decreases its chromatic index; The Critical Graph Conjecture stated that any such graph has odd order – It has been proved false.
* Algebraic formulation: A 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.
@ Directed: Gelfand et al LMP(05) [non-commutative algebra and polynomial]; Fehr et al DM(06) [Cayley digraphs, metric dimension]; Rizzi & Rospocher DM(06) [partially directed and directed]; Boudabbous & Ille DM(07) [critical and infinite].
@ Planar: Osthus et al JCTB(03) [counting, random]; Bouttier et al NPB(03)cm, Di Francesco m.CO/05 [geodesic distance].
@ Bipartite: Greenhill et al JCTB(04) [hamiltonian decomposition].
@ Regular: Wormald in(99) [random]; Bagchi DM(06) [strongly regular]; Kim et al DM(07) [random, small sugbraphs]; Manikandan & Paulraja DM(08) [Hamilton cycle decompositions of tensor products].
@ Realizations in R3: Robertson et al BAMS(93); Taniyama Top(94).
@ Other types: Hoffman DM(04) [partitions into k-stars]; Ding & Chen DM(04) [doubly connected]; Koolen et al EJC(04) [spherical]; Bokal et al DM(05) [chromatic-index-critical]; Marshall EJC(06) [homomorphism bounded classes of graphs]; Chartrand et al DM(06) [uniformly cordial]; Britton et al JSP(06) [generating graphs with given degree distribution]; Cardinal et al CG(08) [geometric, local properties].

Random Graphs > s.a. ising model; networks.
* Idea: A random graph is an ensemble of graphs, defined by some probability distribution on the set of graphs.
* History: First explored systematically in the 1960s by Erdös and Rényi, with whom a significant theory emerged; A quantum leap occured in the 1980s with the application of martingale inequalities to settle previously intractable problems, such as the determination of the chromatic number of a random graph.
@ General references: Gilbert AMS(59); Janson et al 00; Bollobás 01; Penrose 03 [geometric]; Bonato & Delic EJC(04) [infinite, orientations]; Burda et al PhyA(04) [statistical mechanics]; Engel et al JSP(04) [large deviations]; Simonovits & Sós DM(05) [levels of randomness].
@ Random planar graphs: McDiarmid et al JCTB(05); McDiarmid JCTB(08) [on surfaces].
@ Special topics: Higuchi NPB(99) [Hamiltonian cycles]; Wormald in(99) [random regular graphs]; Destri & Donetti JPA(02)cm [random trees, spectral dimension]; Cameron DM(05) [strong small index property].
@ Generalizations: Coulomb & Bauer JSP(04) [different statistical weight]; Lovász & Sós JCTB(08) [quasirandom].

Graphs Embedded in Manifolds > s.a. Gabriel Graph; types of manifolds [families converging to graphs].
* Determined by sets of points: Some possibilities are -graphs, and (the 1-skeletons of) Delaunay triangulations and Voronoi complexes; More generally, nearest-neighbor-type graphs include the k-nearest-neighbours graph, the Gabriel graph, the minimal directed spanning forest, and the on-line nearest-neighbour graph.
* Theta-graph: Determined by a finite set of points in R2.
@ Types of graphs and embeddings: Veltkamp CG(92) [-neighborhood graph, 2-parameter family]; Felsner Ord(03) [geodesic embeddings]; Kramer & Lorente JPA(02)gq/04 [2D spin networks, and duals]; Bose et al CG(04) [ordered -graphs]; Balister et al AAP(05) [random k-nearest-neighbour]; Karpenkov mp/05 [Möbius energy]; Suzuki JCTB(07) [graphs that triangulate a surface and quadrangulate another surface]; Wade AAP(07) [random nearest-neighbour-type graphs].
@ Types of manifolds: Kawarabayashi et al JCTB(03) [on surfaces with high representativity].

Generalizations of Graphs
* Quantum graph: A graph considered as a (singular) one-dimensional variety and equipped with a second-order differential Hamiltonian H (a "Laplacian") with suitable conditions at the vertices.
$ Hypergraph: A pair (X, A), with X a non-empty set, A a covering of X.
@ Hypergraph: Berge 73, 89.
@ Quantum graphs: Barra & Gaspard JSP(00)qp [level spacing distribution]; Dabaghian et al JETPL(01)qp [and chaos], & Blümel qp/03, qp/03, qp/03 [analytically solvable]; Schmidt et al JPA(03) [Green functions]; Kuchment JPA(05)mp/04 [spectral properties]; Tanner qp/05 [and quantum random walks]; Kurasov & Nowaczyk JPA(05) [inverse spectral problem]; Exner et al RVMP(07) [random potential, localization]; Fulling et al a0708 [index theorems]; Kuchment a0802 [rev]; Gavish & Smilansky JPA(07)-a0807 [spectral theory, and length spectrum].
@ Non-commutative: Filk IJTP(00) [distance function].

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