Graph Invariants and Functions

In General > s.a. dimension; 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.
* Girth: The length of the shortest cycle contained in a graph.
* Total chromatic number: The minimum number _T(G) of colours needed to colour the edges and the vertices of G so that incident or adjacent elements have distinct colours.
* Lattice dimension: The smallest number d such that G may be isometrically embedded into the d-dimensional integer lattice Z^d.
* 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: Chromatic number; Length of longest cycle.
@ General references: Yokota Top(96); Rudolph qp/02 [physical].
@ Chain polynomial: Read & Whitehead DM(99) [def]; Read DM(03) [properties].
@ Tuttle polynomial: Read & Whitehead DM(02); Woodall DM(02); Goodall JCTB(06).
@ Other polynomials: Sokal CPC(04)cm/00 [zeros of chromatic polynomials]; Arratia et al JCTB(04) [interlace polynomial]; Bouchet DM(05).
@ 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].
@ Chromatic number: Xie & Yang DM(03); Johnson & Rodger EJC(05).
@ Related topics: Knuth EJC(94) [Lovász no]; Major NPB(99) [and Chern-Simons theory]; Courcelle DM(04) [clique width]; Székely DM(04) [crossing no]; Sanchis DM(04) [domination numbers]; Chandran & Sivadasan DM(07) [Hadwiger conjecture].
> Related topics: see euler characteristic; knot invariants.

Metric and Geometrical Concepts
* Distance in 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] = df   1} .

@ Metric: Davies JFA(93) [and heat kernel for discrete laplacian]; Buyalo mp/03 [with non-positive curvature]; Forgy & Schreiber mp/04 [causal].
@ Connes metric: Filk IJTP(00); Requardt JPA(02)mp/01.
@ 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]; > s.a. differential geometry.

Other Natural Structures on Graphs
* 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), Stevanovic JCTB(04) [bounds].

Main page – Abbreviations – Journals – Comments – Other sites – Acknowledgements
Send feedback and suggestions to bombelli at olemiss.edu – Modified 23 may 2008