|M.Sc Student||Rakita Vsevolod|
|Subject||On Weakly Distinguishing Graph Polynomials|
|Department||Department of Mathematics||Supervisor||PROFESSOR EMERITUS Johann Makowsky|
|Full Thesis text|
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.