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 19
sep
2017