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 R__

@

@

**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.

@ __Books__: Janson et al 00;
Bollobás 01; Penrose 03 [geometric]; Durrett 06;
Frieze & Karoński 15; van der Hofstad 16.

@ __General references__: Gilbert AMS(59);
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]; Chatterjee & Varadhan EJC(11) [large deviation principle].

@ __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 PRE(16)-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 *P*_{n} of
labelled planar graphs with *n* vertices
satisfies *n*! (26.1)^{n+o(n)}
≤ |*P*_{n}| ≤ *n*!
(37.3)^{n+o(n)}, and almost
all graphs in *P*_{n} 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 S^{2} 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 page
– abbreviations
– journals – comments
– other sites – acknowledgements

send feedback and suggestions to bombelli at olemiss.edu – modified 4 apr 2018