Study On Some Problems Of Graph Polynomials

This thesis consists of five chapters. In the first half of this thesis, we mainly focus on the computation of the Tutte polynomials of several serf-similar network models. In the second half of the thesis, we study which graph invariant and what kind of graphs are determined by the subgraph component polynomial. Also, we discuss the distinguishing power of this polynomial.In the first chapter, the background, motivation and current situation of the application of graph polynomial in complex network are introduced.In the second chapter, we make preparations for the subsequent chapters. We present some basic definitions which are necessary.In the third chapter, we study the computation of the Tutte polynomial.(1). F. Comellas et al [23] developed a kind of small-world network model which is self-similar, and they obtained the number of spanning trees of this network model Mn [24]. Making use of the subgraph-decomposition method, we study the Tutte polynomial of Mn and obtain a recursive expression. Then we derive exact expressions for the flow polynomial and the number of spanning tree from this recursive formula.(2). Zhang et al [82] first study the Farey graph Gn as a complex network model and they count the number of spanning trees by applying the matrix-tree theorem [83]. Based on the special structure of the Farey graph, we obtain a recursive expression for T(Gn; x, y). Moreover, we study the flow polynomial, the chromatic polynomial and the number of spanning trees of Gn, and we get exact expressions for these graph invariants.(3). Zhang et al [81,84] compute the number of spanning trees of the Apollonian network by different methods. We change our mind this time. We do not compute directly the Tutte polynomial of the Apollonian network like before. We computed the Apollonian dual graph instead. Using the connection between the Apollonian dual graph and Hanoi graph, we can express the Tutte polynomial of the Apollonian dual graph in term of the Tutte polynomial of the Hanoi graph.(4). We note that most network model are modular. It is a natural way to construct modular by pasting vertices. Then it is meaningful to study the Tutte polynomial of two point join graph G:H. We find that T(G:H; x, y) can obtain from the Tutte polynomials of G, H and some of their subgraphs. Furthermore, using this result, we compute the spanning trees of the pseudo-fractal scale-free web and the generalized (2,2)-flower graph. Also, we study the Tutte polynomial of the polygonal chain and the book graph.In the fourth chapter, we study the subgraph component polynomial Q(G;x,y). Motivated by social and biological networks, Tittmann et al [75] introduced this bivariate polynomial. Just like the Tutte polynomial, the sub-graph component polynomial contain rich combinatorial information, such as the order, the size and the number of components. We show that several other graph invariants, such as the connectivity and the number of cycles of length four in a regular bipartite graph are also determined by the subgraph compo-nent polynomial. Then, we prove that several well-known families of graphs are determined by the polynomial Q(G;x,y). For example, the friendship graph, the book graph and the n-cube. Moreover, we study the distinguishing power and find simple graphs which are not distinguished by the subgraph component polynomial but distinguished by the characteristic polynomial, the matching polynomial and the Tutte polynomial. These are partial answers to three open problems proposed by Tittmann et al.In Chapter 5, we summarize the main work of this thesis and raises several problems that need further study.