# Graph invariant that encodes number of subgraphs with $i$ vertices and $j$ edges

Suppose we have invariant of graph $G$ that tells us number of subgraphs with $i$ vertices and $j$ edges for every setting of $i$ and $j$. Is there a name for it?

I searched for "subgraph polynomial", but that comes up as something else.

-
A minor comment for future reference: you can use TeX mode in the title, and doing so improves the readability of the question. –  Asaf Karagila Jan 16 '11 at 10:49

## 2 Answers

See this (MO question that is similar). I don't think there is any name for it.

-

Have you ever hear about the Tutte Polynomial $T(G;x,y)$ ? it is defined for any graph $G$ (and even defined for matroids) and it has many evaluations which count combinatorial structures related to $G$. Also, many other polynomials related to $G$ are just the Tutte polynomial under some clever substitution (like the chromatic polynomial and the flow polynomial) A good starting point to learn about $T(G;x,y)$ is

http://en.wikipedia.org/wiki/Tutte_polynomial

It contains many good references on the subject. A last word: Computing the Tutte polynomial is #P-complete in almost any point of the complex plane.

-