Graph polynomials are powerful and well studied invariants of graphs. Much

interest has been shown in whether certain graph polynomials P(G) of a

graph G characterise G. The most common approach to this question is

finding P-unique graphs, that is graphs G such that for all graphs H, if

P(G) = P(H) then G and H are isomorphic.

We say that a graph G is P-unique if for no graph H that is non-isomorphic

to G, P(G) = P(H). If G is not P-unique and H is a graph that is not

isomorphic to G such that P(G) = P(H), we say G and H are P-mates. A

graph polynomial P is a complete graph invariant if all graphs are P-unique,

and otherwise it is an incomplete invariant. All graph polynomials studied

in the literature are known to be incomplete.

We say that a graph polynomial P is α-complete if when selecting a

graph with n vertices uniformly at random the probability of selecting a

P-unique graph tends to α. When P is 1-complete, we say P is almost

complete. When P is 0-complete, we say P is weakly distinguishing.

Bollobas et al. conjectured that the Tutte and chromatic polynomials

are almost complete.

In this thesis, we show that the clique polynomial and the independence

polynomial are weakly distinguishing. Furthermore, we show that generating

functions of induced subgraphs with property C are weakly distinguishing

for an infinite number of properties C. The same holds for the harmonious

polynomial and generalised harmonious polynomials.

Extending the definition of weakly distinguishing graph polynomials, we

say that a graph polynomial P is weakly distinguishing on a graph property

C if when selecting a graph with n vertices uniformly at random from the

property C, the probability of selecting a P-unique graph tends to 0.

We give sufficient conditions on a graph property C for the Tutte, chromatic,

domination, characteristic, matching and other graph polynomials to

be weakly distinguishing on C.