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