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 *k*th power *G ^{ k}* of a graph

*

*

*

@

@

**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 *D*_{ij}:= |*v*_{i}–*v*_{j}|,
where *v*_{i} 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

*d*_{C}(*n*, *n*'):=
sup{|*f*_{n'} – *f*_{n}| | || [*D*, *f*]
|| = || d*f* || ≤ 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 a1402; Rovelli a1408 [Lorentzian, and loop quantum gravity].

@ __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];
Lorente gq/04-in
[curvature]; 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 19
dec 2016