The Polynomial Uniqueness Of Graphs

The study of graph polynomials has been an active research topic for many years. It serves as a bridge between graph theory and traditional algebra. Since the coefficients of polynomials often contain rich combinatorial information, the study of graph polynomials provides new avenues to understand the complicated structures of graphs and graphic parameters. It is natural to ask what kind of graphs are determined by their polynomials. In particular, what kind of graphs have their structures entirely encoded in a graph polynomial? In other words, can we find families of graphs that are uniquely determined by a given polynomial? In this thesis, we mainly consider these problems.There are three important graph polynomials in graph theory, they have a close relationship with each other: chromatic polynomial, Tutte polynomial and flow polynomial. The flow polynomial can be considered as the dual of the chromatic polynomial, and both of them are evaluations of the Tutte polynomial. There is extensive research on graphs uniquely determined by their chromatic polynomials and more recently on their Tutte polynomials, but rather spotty research on graphs uniquely determined by their flow polynomials or the combination of both chromatic and flow polynomials. This thesis is an initiation of investigation in this area.The thesis consists of two parts. The first part contributes to flow polynomials of graphs and graphs uniquely determined by chromatic and flow polynomials together, which is an initiation of investigation in this direction; the second part is devoted to graphs determined entirely by their Tutte polynomials.The first part of this thesis consists of Chapters 2 and 3. In Chapter 2, we focus on the flow polynomials of graphs. We study the coefficients of flow polynomial and prove that if two connected cosimple graphs have the same flow polynomial, then they have the same number of vertices and edges, the same edge-connectivity and the same number of minimum bonds. Using the information contained in flow polynomial of graphs, we prove that the dual of generalizedθ-graph, K₅ and K_3,3 can be entirely determined by their flow polynomials.In Chapter 3, we show that the ladders, M(o|¨)bius ladders and square of cycles are determined by their chromatic polynomial and flow polynomial together. A direct consequence of our theorems is a result of de Mier and Noy that these classes of graphs are determined by their Tutte polynomials.The second part is Chapter 4, which is concerned about the research on two classes of graphs: one is the twisted wheel W_k1,k2 (see Figure 4.2) and the other class of graphs is called the double half-wheel W_h(k₁,k₂) (see Figure 4.3 (b)). To simplify the structure of the graphs, we introduce a concept of triangle-graph whose idea is similar to line-graph. Using the information contained in Tutte polynomial of graphs, we show that both of two classes of graphs can be determined by their Tutte polynomials.