Tutte Uniqueness Of Several Kinds Of Line 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.In the articles which study the properties and applications of a graph, some polynomials such as the matching polynomial, the chromatic polynomial, the flow polynomial, the Tutte polynomial, the genus distribution polynomial, and the total embedding distribution polynomial are used to describe the graphs. Among which, the chromatic polynomial, the flow polynomial, and the Tutte polynomial are three important graph polynomials in the graph theory. They have a close relationship with each other. The flow polynomial can be considered as the dual of the chromatic polynomial, and both of them are evaluations of the Tutte polynomial. Therefore, many studies in recent years are focused on the Tutte polynomial and graphs that can determined uniquely by the Tutte polynomial.This paper mainly studies the uniqueness of Tutte polynomial of line graphs. We say that a graph G is T-unique if any other graph having the same Tutte polynomial as G is isomorphic to G. The Tutte polynomial of a graph is an important part of graph theory. It not only has many relationships with matriod and chromatic polynomials, but it also contains a lot of information about the graph, such as the number of vertices, the number of edges, and so on. What is more, some families of graphs are determined by their Tutte polynomial.Some scholars have done a lot of research about the uniqueness of Tutte polynomial, and the uniqueness for several families of graphs and line graphs have been discussed. But little is known about the uniqueness of Tutte polynomial for most line graphs.In this paper, we study the uniqueness of Tutte polynomial of two kinds of line graphs--the line graph of Ladders L(Ln) and the line graph of the dodecahedron on the basis of the previous research.In chapter one, we introduce the concepts and background of the uniqueness of Tutte polynomial. In addition, we give the structure and the content of each chapter of this paper briefly.In chapter two, we study the uniqueness of Tutte polynomial of the line graph of Ladders L(Ln) and obtain the following conclusion:If H has the same Tutte polynomial with L(Ln) and H is a plane graph, then H is isomorphic to L(Ln)for n≥6n and n≠4i, i=2,3…; and they are not T-unique for n=4i and i=2,3….In chapter three, we prove the line graph of the dodecahedron is T-unique.