Graph Invariants |

**In General** > s.a. hilbert
space; lattice [number of paths].

* __Betti deficiency__: The number
*ξ*(*G*):= min_{T} *ξ*(*G*,*T*),
where *T* is a spanning tree of the connected graph *G*, and *ξ*(*G*,*T*)
the number of components in *G* \ *E*(*T*) with odd number of edges.

* __Density__: The ratio
of the number *m* of edges to the number *n* of vertices; For a sparse graph
*m* ≈ *n*, for a dense graph *m* ≈ \(n^2\).

* __Dimension__: The dimension of a graph
is the least integer *n* such that there exists a "classical representation"
of the graph in the Euclidean space of dimension *n* with all the edges having unit length;
> s.a. Wikipedia page.

* __Lattice dimension__:
The smallest number *d* such that *G* may be isometrically
embedded into the *d*-dimensional integer lattice \(\mathbb Z^d\).

* __Metric dimension__: The minimum cardinality of a resolving set of *G*;
> s.a. Wikipedia page.

* __Diameter of a graph__: The greatest distance between any pair of vertices.

* __Geodetic number__: The size of a minimum geodetic set in *G*.

* __Hadwiger number__: The number
*η*(*G*) is the largest integer *h* such that the complete graph
on *h* nodes is a minor of *G*; Equivalently, *η*(*G*)
is the largest integer such that any graph on at most *η*(*G*) nodes
is a minor of *G*; Hadwiger's conjecture states that for any graph *G*,
*η*(*G*) ≥ *χ*(*G*), where *χ*(*G*)
is the chromatic number of *G*.

* __Other invariants__: Girth (the length
of the shortest cycle contained in a graph); Length of longest cycle.

@ __General references__: Yokota Top(96);
Rudolph qp/02 [physical].

@ __Maximum genus__: Xuong JCT(79) [and Betti deficiency];
Huang DM(03),
DM(03) [bound].

@ __Dimension__: in Smolin pr(88) [and variety];
Nowotny & Requardt JPA(98)ht/97;
Eppstein EJC(05) [lattice dimension, algorithm];
Boza & Revuelta ENDM(07) [examples];
Tomescu DM(08)
[discrepancy between metric dimension and partition dimension];
Giasemidis et al JPA(12)-a1202 [spectral vs Hausdorff dimension];
Arumugam & Mathew DM(12) [fractional metric dimension];
House DM(13) [a 4D graph has at least 9 edges];
> s.a. types of graphs [random, spectral dimension].

@ __Related topics__: Knuth EJC(94) [Lovász number];
Major NPB(99) [and Chern-Simons theory];
Courcelle DM(04) [clique width];
Székely DM(04) [crossing number];
Sanchis DM(04) [domination numbers];
Chandran & Sivadasan DM(07) [Hadwiger conjecture];
Krajewski et al JNCG(10)-a0811 [and quantum field theory];
Crown DM(09) [cyclic coloring complex, homology];
Asté et al DM(10) [Grundy number];
Barlow et al CPC-a1001 [cover time];
Dvořák et al EJC(11) [Randić index].

> __Related topics__: see euler characteristic;
knot invariants.

> __Online resources__:
see (Gromov) Graph Hyperbolicity.

**Polynomials**

@ __Chain polynomial__:
Read & Whitehead DM(99) [def];
Read DM(03) [properties].

@ __Tutte polynomial__:
Read & Whitehead DM(02);
Woodall DM(02);
Goodall JCTB(06);
Garijo et al EJC(09) [and graph homomorphisms].

@ __Chromatic polynomial__:
Sokal CPC(04)cm/00 [zeros];
Van Bussel et al JPA(10)-a1709 [of random graphs].

@ __Other polynomials__: Arratia et al JCTB(04) [interlace polynomial];
Bouchet DM(05);
Chen & Yang DM(09) [flow polynomials].

**Chromatic Number**

* __Total chromatic number__: The
minimum number *χ*_{T}(*G*)
of colors needed to colour the edges and the vertices of *G* so that incident
or adjacent elements have distinct colors.

@ __References__: Xie & Yang DM(03);
Johnson & Rodger EJC(05);
Mohar & Špacapan EJC(12) [degenerate and star chromatic numbers].

**Topology on a Graph** > s.a. cell
complex; morse theory.

* __Weakly compatible topology__:
A topology on { · } is compatible with the graph *G* = ({ · },
{ ↑ }) if for every finite subgraph *A* ⊂ *G*, *A* is
connected iff it is topologically connected.

* __Compatible topology__: A topology
on { · } is compatible with the graph *G* = ({ · }, { ↑ })
if for every subgraph *A* ⊂ *G*, *A* is connected iff it
is topologically connected.

* __Result__: A weakly compatible
topology on { · } determines the graph uniquely.

@ __References__: Neumann-Lara & Wilson Ord(95) [compatibility].

**Other Natural Structures on Graphs** > s.a. graph theory [ranking, colorings, etc];
subsets and operations on graphs [metric and geometrical concepts].

* __Adjacency matrix__: Given
a labeling of a graph, \(M_{ij} = 1\) if there is an edge between *i* and
*j*, 0 otherwise; If the graph is directed (e.g., a poset), \(M_{ij} = 1\)
if there is an edge from *i* to *j*; For the *k*-th power
of the adjacency matrix, \((M^k)^~_{ij}\) is the number of paths of length *k*
between *i* and *j*.

* __Eigenvalues__: The eigenvalues
of a graph are the eigenvalues of its adjacency matrix.

@ __Adjacency matrix__: Dobrynin DM(04) [rank].

@ __Eigenvalues__: Das & Kumar DM(04),
Stevanović JCTB(04) [bounds].

main page
– abbreviations
– journals – comments
– other sites – acknowledgements

send feedback and suggestions to bombelli at olemiss.edu – modified 29 nov 2018