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

* 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 abE(G) and vwE(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) | aV(G), vV(H)}, where the vertex (a,v) is adjacent to (b,w) if abE(G), or a = b and vwE(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:= |vivj|, 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 pageabbreviationsjournalscommentsother sitesacknowledgements
send feedback and suggestions to bombelli at – modified 26 apr 2021