Deleted:Deletion–contraction formula

From WikiAlpha
Jump to: navigation, search
The below content is licensed according to Creative Commons Attribution-ShareAlike License contrary to the public domain logo at the foot of the page. It originally appeared on http://en.wikipedia.org. The original article might still be accessible here. You may be able to find a list of the article's previous contributors on the talk page.

In graph theory, a deletion-contraction formula / recursion is any formula of the following recursive form:
<math>f(G) = f(G\smallsetminus e) + f(G / e)</math>
Here G is a graph, f is a function on the set of vertices of that graph, e is any edge, G&nbsp;\&nbsp;e denotes edge deletion, and G&nbsp;/&nbsp;e denotes contraction. Tutte refers to such a function as a W-function.[1] The formula is sometimes referred to as the fundamental reduction theorem.[2] In this article we abbreviate to DC.

R. M. Foster had already observed that the chromatic polynomial is one such function, and Tutte began to discover more, including a function &fnof;&nbsp;=&nbsp;t(G) counting the number of spanning tree of a graph (also see Kirchhoff's theorem). It was later found that the flow polynomial is yet another; and soon Tutte discovered an entire class of functions called Tutte polynomials (originally referred to as 'dichromates') that satisfy DC.[1]

Properties

As some illustrative examples, the number of spanning trees t(G) satisfies DC.[3] Note below we use a slightly different definition of arboricity that refers to spanning trees (as opposed to forests):
Template:Collapsible sectionThe chromatic polynomial <math>\chi_k(G)</math> counting the number of k-colorings of G is DC, but for a slightly modified formula (which can be made equivalent):[1]

<math>\chi(G) = \chi(G\smallsetminus e) - \chi(G / e)</math>Template:Collapsible sectionThis above property can be used to show that the chromatic polynomial <math>\chi_k(G)</math> is indeed a polynomial in&nbsp;k. We can do this via induction on the number of edges and noting that in the base case where there are no edges, there are <math>k^{|V(G)|}</math> possible colorings (which is a polynomial in&nbsp;k).

Deletion-contraction algorithm

Template:Empty section

See also

Citations

  1. 1.0 1.1 1.2 Tutte, W.T. (January 2004). "Graph-polynomials". Advances in Applied Mathematics 32 (1-2): 5–9. doi:10.1016/S0196-8858(03)00041-1. https://linkinghub.elsevier.com/retrieve/pii/S0196885803000411. 
  2. Template:Harvtxt
  3. "Deletion-contraction and chromatic polynomials". https://www.math.wisc.edu/~svs/475/chromatic.pdf.