Study On Linear Parameters And Matching Polynomials Of Graphs

Let G be a graph of order n with vertex set V(G)={v1, V2,...,vn}. The adjacency matrix of G is an n x n matrix A(G)=(a,ij)n×n, where aij is the number of edges joining Vi and Vj in G. The eigenvalues λ1, λ2, λ3,…λn of A(G) are said to be the eigenvalues of G which form the spectrum of this graph. The numbers of positive eigenvalues, negative eigenvalues and zero eigenvalues of G are called positive inertia index, negative inertia index and nullity of G respectively, and are denoted by p(G), n(G) and η(G), respectively. The rank of G, written as r(G), is the number of nonzero eigenvalues of G. The signature of G, written as s(G), is defined as p(G)-n(G). A matching of G is a spanning subgraph of G in which each component is an isolated edge or an isolated vertex. A t-matching is a matching with t edges. The matching polynomial of G is defined as where p(G, t) denotes the number of t-machings in G.This dissertation consist of six chapters.Chapter1is an introduction which contains some basic concepts and conclusions in graph spectra theory and matching polynomial theory.Chapter2presents methods to calculate positive inertia indexes and negative inertia indexes of trees, unicyclic graphs, bicyclic graphs, and two kinds of tricyclic graphs.Chapter3characterizes graphs with a rank no more than6, and graphs with a rank no more than8and with pendent vertices.In Chapter4, the inequality e{G)≥p(G) is proved for any graph G, where ε(G) is the complete multipartite graph edge decomposition number of G, a graph G with p(G)=n-2is characterized, a tree G with p(G)=k is characterized inductively (where k is an arbitrary nonnegative integer number), a graph G with n{G)≤<3is characterized, and a graph G with n{G)≤4and with pendent vertices is also characterized. An inequality about the signature of a graph G is proved, and a conjecture related is also proposed.In Chapter5a graph whose second largest matching root is M2(G)=1or who has at most two positive matching roots is characterized.In Chapter6a necessary and sufficient condition for two graphs with the maximum matching root no more than2to be matching equivalence is given. Two integral formulas and two summation formulas about the Hosoya index are given by using the matching polynomial and the rook polynomial, the number of the permutations which satisfies some inequality conditions is counted by using the rook polynomials.