Special Types of Graphs, Graph Embeddings Note: This page is not about graphs of functions, or graphical representations of data, but about the graphs studied by graph theory.

Connected Graphs
$ Complete graph: A graph in which every pair of vertices is connected by a unique edge.
$ Doubly connected graph: A connected graph whose complement is also connected.
$ Hamiltonian graph, def: A (connected) graph that has a Hamiltonian cycle, i.e., one that goes through every vertex exactly once.
* Hamiltonian graph, results: Determining whether a graph is Hamiltonian is known to be an NP-complete problem, and no satisfactory characterization for these graphs has been found; Dirac showed in 1952 that every graph of order n is Hamiltonian if any vertex is of degree at least n/2.
@ References: Ding & Chen DM(04) [doubly connected].

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

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

$ Simple graph: 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; > s.a. Claw Graph.
* Prime graph: Graphs that cannot be (non-trivially) obtained from other graphs by Cartesian multiplication.
* 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 Δ colors (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.
@ 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]; Brinkman DM(13) [algorithm to generate regular directed graphs].
@ Bipartite: Greenhill et al JCTB(04) [hamiltonian decomposition].
@ Regular: Bagchi DM(06) [strongly regular]; Manikandan & Paulraja DM(08) [Hamilton cycle decompositions of tensor products].
@ Realizations in R3: Robertson et al BAMS(93); Taniyama Top(94).
@ Generating graphs with given degree distribution: Britton et al JSP(06); Kim et al JPA(09).
@ Other types: Hoffman DM(04) [partitions into k-stars]; 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]; Cardinal et al CG(08) [geometric, local properties]; Li JCTA(08), Pouzet & Zaguia Ord(09) [prime]; Nešetřil & Ossona de Mendez EJC(11) [nowhere dense graphs]; Bermudo et al DM(13) [hyperbolic]; Benvenuti & Piergallini EJC(13) [automorphisms of trivalent graphs on 2D surfaces]; > s.a. Snarks.

Random Graphs > s.a. networks [including small-world graphs]; random tilings; types of posets.
* 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]; Durrett 06; Chatterjee & Varadhan EJC(11) [large deviation principle]; Frieze & Karoński 15 [intro].
@ Random planar graphs: McDiarmid et al JCTB(05); McDiarmid JCTB(08) [on surfaces]; Drmota et al JCTA(11) [degree distribution].
@ Random regular graphs: Wormald in(99); Kim et al DM(07) [small sugbraphs]; Elon JPA(08) [Laplacian eigenvectors]; Ding et al a1310 [maximum independent sets].
@ Special topics: Higuchi NPB(99) [Hamiltonian cycles]; Destri & Donetti JPA(02)cm [random trees, spectral dimension]; Cameron DM(05) [strong small index property]; Grimmett & Janson EJC-a0709 [random even subgraphs of a finite graph]; Coja-Oghlan et al JCTB(08) [chromatic number]; van den Esker et al JSP(08) [graph distance between random vertices]; Heydenreich & van der Hofstad PTRF-a0903 [on high-dimensional tori]; Newman PRL(09) [modeling clustering/transitivity]; Ergün & Kühn JPA(09) [modular, spectra]; Gaudilličre et al JSP(11) [cliques and phase transitions].
@ Other random graphs: Coulomb & Bauer JSP(04) [different statistical weight]; Lovász & Sós JCTB(08) [quasirandom]; Garlaschelli NJP(09)-a0902 [weighted random graphs]; Ferrari et al a1002 [Gibbs random graphs]; Müller & Richard CJM(12)-a1005 [randomly-colored graph]; Kotorowicz & Kozitsky ConMP(11)-a1106, a1503 [motif-based hierarchical random graphs]; Yin JSP(13)-a1208 [exponential random graphs, critical phenomena].
@ And physics: Janson & Luczak JMP(08) [susceptibility]; Avetisov et al a1607 [canonical ensemble]; > s.a. critical phenomena; ising model.

Graphs Embedded in Manifolds > s.a. Gabriel Graph; statistical geometry; types of manifolds [families converging to graphs].
* Planar graphs: 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.
* Graphs embedded in a 2-sphere: If a graph can be embedded into S2 without crossing, it is topologically equivalent to a convex polytope; But any convex polytope can be represented by a Schlegel diagram on the plane without crossing.
* 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; A general concept is that of empty-region graph.
* Theta-graph: Determined by a finite set of points in \(\mathbb R\)2.
@ Planar graphs: Osthus et al JCTB(03) [counting, random]; Bouttier et al NPB(03)cm, Di Francesco m.CO/05 [geodesic distance]; Gudkov et al a0907 [characterization].
@ 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 MN(06)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]; Cardinal et al CG(09) [empty-region graphs]; Aronov et al CG(11) [witness graphs].
@ Types of manifolds: Kawarabayashi et al JCTB(03) [on surfaces with high representativity]; Chapuy et al JCTA(11) [on a 2D surface of genus g, enumeration]; Ikeda T&A(12) [hyperbolic spatial embeddings in closed connected orientable 3-manifolds].


main pageabbreviationsjournalscommentsother sitesacknowledgements
send feedback and suggestions to bombelli at olemiss.edu – modified 13 jul 2016