The Matching Polynomials Of Hypergraphs And Their Applications In Spectral Hypergraph Theory

Spectral graph theory mainly studies the relationship between the spectral property and the structural property of graphs and discusses how the structural property of a graph is characterized by its spectral property,it has been an important research field of algebraic graph theory and combinatorial matrix theory.With the wide application of hypergraph in data mining,large-scale integrated circuit design,network and computer,the study of spectral hypergraph theory has attracted more and more attention.The matching polynomials of hypergraphs and spectral perturbations of hypertrees are studied and the ordering of hypertrees with given parameters by spectral radius are determined in this paper.Hypergraphs and tensors are natural generalizations of graphs and matrices.However,the degree of characteristic polynomial of a hypergraph is very high relative to its order,and very little is known about it up to now.Recently,Zhang et al.established a relation between the eigenvalues of hypertrees and the associated polynomial,which we modified and call it the matching polynomial of hypergraphs.The work in this paper is based on the polynomial.The main content of this thesis is as follows.(1)In Chapter 1,we first present the backgrounds and research progresses of the study work about spectral hypergraph theory,and then give the basic definitions,notations and usual methods.(2)In Chapter 2,We first redefine matching polynomial of hypergraphs,and then give some recurrence relations of matching polynomial of hypergraphs.At the same time,the ordering on forests introduced by Lováasz and Pelikáan is extended to hyperforests.(3)In Chapter 3,the grafting transformations on first studied graphs by Li and Feng is extended to the hypertrees by using the recurrence relations of matching polynomial of hypertrees,and then the minimal hypertree is characterized.At the same time the effect on the spectral perturbation of hypertree by grafting edges in various situations is also discussed.(4)In Chapter 4,we determine the second smallest spectral radius of hypretree with m edges and the first [d/2]+1 largest spectral radii of hypertrees among all hypertrees with size m and diameter d.(5)In Chapter 5,we determine the hypertrees with the first two largest spectral radii among all hypertrees with medges and given size of matching.(6)In Chapter 6,we determine the first two largest spectral radii of hypertrees withmedges and given strong stability number.Furthermore,we Characterize the largest spectral radius of hypertree with given size of edge and stability number(resp.domination number).