Special Types of Graphs, Graph Embeddings| Special Types of Graphs, Graph Embeddings |
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.
@ 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].
@ Exponential random graphs:
Yin JSP(13)-a1208 [critical phenomena];
Akara-pipattana et al a2102 [emergent Riemannian geometry].
@ 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].
@ 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(11)-a0903 [on high-dimensional tori];
Newman PRL(09) [modeling clustering and transitivity];
Ergün & Kühn JPA(09) [modular, spectra];
Gaudillière et al JSP(11) [cliques and phase transitions];
Jnane et al a2004 [growing using quantum walks].
@ 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
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];
Fendley & Krushkal a1902 [on a torus, polynomial identities].
main page
– abbreviations
– journals – comments
– other sites – acknowledgements
send feedback and suggestions to bombelli at olemiss.edu – modified 28 feb 2021