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