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.

@ __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 *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 13
jul 2016