Subsets and Operations on Graphs| Subsets and Operations on Graphs |
Special Subsets
> s.a. Cycle; graph invariants;
graph types; ramsey theory.
* Hamiltonian cycle:
A closed path that visits every vertex once and only once.
* Minor: An undirected graph
H is called a minor of a graph G if H can be formed
from G by deleting edges and vertices and by contracting edges.
* Interval: The interval
I[u,v] is the set of all vertices lying in some
u-v shortest path of G.
* Geodetic set: A set S
of vertices of a graph G is a geodetic set if every vertex of
G lies in at least one interval between vertices of S;
(The geodetic number of G is the size of a minimum geodetic set in
G).
* Independent set or stable set:
A set of vertices in a graph, no two of which are adjacent; > s.a. Wikipedia
page.
* Hole: A hole in a graph
is an induced subgraph which is a cycle of length at least four.
* Resolving set: A set of
vertices W resolves a graph G if every vertex in G
is uniquely determined by its distances ("coordinates") to the vertices
in W; (The minimum cardinality of a resolving set of G is called
the metric dimension of G).
@ Hamiltonian cycles:
Higuchi MPLA(98) [counting, planar].
@ Minors:
Robertson & Seymour JCTB(04);
Lovász BAMS(06);
Cai et al a1406
[practical heuristic for finding graph minors].
@ Related topics:
Kostochka & Tashkinov Ord(03) [decomposition into long paths];
Addario-Berry et al JCTB(08) [bisimplicial vertices in even-hole-free graphs];
Dourado et al DM(09) [intervals, convex sets and hulls],
DM(10) [geodetic number];
Woodroofe JCTA(11) [Erdős-Ko-Rado property, in terms of the graph's independent sets];
Goddard & Henning DM(13) [independent dominating sets].
Operations
* Power of a graph:
The kth power G k of a graph
G is the graph with the same vertex set as G, such that two
vertices are adjacent in G k if and
only if their distance is at most k in G; > s.a.
graphs in physics [Laplacian eigenvalues].
* Edge contraction:
An operation which removes an edge from a graph and merges the two vertices
previously joined by that edge.
* Direct product: The direct
product of graphs G = (V(G), E(G))
and H = (V(H), E(H)) is the graph
G × H with vertex set V(G) ×
V(H), where the vertex (a,v) is adjacent to
(b,w) in if ab ∈ E(G) and
vw ∈ E(H).
* Lexicographic product:
The lexicographic product of graphs G and H is the graph
G · H with vertex set V(G) ×
V(H) = {(a,v) | a ∈ V(G),
v ∈ V(H)}, where the vertex (a,v) is
adjacent to (b,w) if ab ∈ E(G), or
a = b and vw ∈ E(H).
@ General references:
Ryjácek JCTB(97),
Kelmans DM(03) [closure];
Saito JCTB(03) [splitting in 4-connected graphs];
Audenaert et al JCTB(07) [symmetric squares];
Klavzar & Severini a0909 [generalized tensor product, for entanglement];
Vallée & Bretto DM(11) [closure preserving Hamiltonicity];
Dorfler & Bullo a1102 [Kron reduction];
Lee et al JCTB(13) [maximum bisections].
@ Graph rewriting:
Behr et al a1612 [rule algebras, types];
> s.a. Wikipedia page.
Metric and Geometrical Concepts
* (Path) distance on a graph:
The distance between graph vertices x and y is defined as
d(x, y):= min{l(p) | paths p
connecting x and y}.
* Other distance on a graph:
Can be defined (i) as Dij:=
|vi−vj|,
where vi is the i-th
column of the adjacency matrix, and | · | the Euclidean norm; or
(ii) as a Connes metric given, for two graph vertices n and n', by
dC(n, n'):= sup{|fn' − fn| | || [D, f] || = || df || ≤ 1} .
* Diameter of a graph:
The greatest distance between any pair of vertices.
@ Distance:
Davies JFA(93) [and heat kernel for discrete Laplacian];
Buyalo mp/03 [with non-positive curvature];
Forgy & Schreiber mp/04 [causal];
in Chang et al EJC(04) [geodetic];
Cáceres et al EJC(08) [Steiner, and convexity];
> s.a. types of graphs.
@ Connes metric / spectral distance: Filk IJTP(00);
Requardt JPA(02)mp/01;
Jovanović & Stanić LA&A(12) [properties and examples];
Gu et al DAM(15)-a1402;
Rovelli a1408 [Lorentzian, and loop quantum gravity].
@ Curvature:
Lorente gq/04-in;
van der Hoorn et al PRR(21)-a2008 [Ollivier curvature of random graphs];
> s.a. curvature.
@ Related topics: Dimakis & Müller-Hoisson JMP(94) [discrete differential calculus];
Cho & Park JMP(97) [linear connections];
Requardt ht/97 [analysis];
Nowotny & Requardt CSF(99)ht/98 [and Planck-scale physics];
Fulek et al DM(11) [diameter bounds];
Keller a1101 [curvature and spectral properties, planar graphs];
Füredi & Kim DM(13) [structure of typical graphs of a given diameter];
Keller a1407 [intrinsic metrics, rev];
> s.a. differential geometry.
main page
– abbreviations
– journals – comments
– other sites – acknowledgements
send feedback and suggestions to bombelli at olemiss.edu – modified 26 apr 2021