Graph Invariants |
In General > s.a. hilbert
space; lattice [number of paths].
* Betti deficiency: The number
ξ(G):= minT
ξ(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