Study Of The Polynomial Of Graph And Its Related Problems

Spectral graph theory is one of the important branch in graph theory,and the study of graph polynomial is a hot research topic in recent years.The graph polynomials are basis for the study of graph spectrum,which have important applications in the field of computer science,physics,chemistry,biology and control engineering.The adjacency matrix of graph G is denoted by A?G?.The Laplacian matrix of graph G is denoted by L?G?.The signless Laplacian matrix of graph G is denoted by Q?G?.These matrices's characteristic polynomial is called adjacency characteristic polynomial,Laplacian characteristic polynomial and signless Laplacian characteristic polynomial,respectively.The eigenvalues with their multiplicities of these characteristic polynomials constitute adjacency spectrum,Laplacian spectrum and signless Laplacian spectrum of graph G,respectively.The corresponding characteristic polynomials and permanental polynomials can be obtained through all kinds of matrices.The corresponding graph spectrum and some indexes can be computed by their characteristic polynomials,and the copermanental graphs can be numerated by their permanental polynomials.In this thesis,the polynomials and applications of some classes of complex graphs are studied:the generalized subdivision-edge corona graph S?G?!???H_i which is constructed by graph G and graphH₁,H₂,?42?,H_m,the subdivision-vertex-vertex join graph G₁"G₂and the subdivision-edge-edge join graph G₁!G₂ generated by graph ₁G and graph ₂G.The adjacency characteristic polynomial,Laplacian characteristic polynomial,signless Laplacian characteristic polynomial and generalized characteristic polynomial of these graphs are obtained and proved by the corresponding properties of these matrices.As the application,we construct infinitely many pairs of A-cospectral and L-cospectral graphs and calculate the number of spanning trees,the Kirchhoff index and the Laplacian energy like invariant of the graphs.Also,we get all the nonisomorphic graphs at most 9 vertices by computer programming,compute all the permanental adjacency polynomials,permanental Laplacian polynomials and permanental signless Laplacian polynomials,and illustrate all the A-,A&???-,L-and Q-copermanental graphs.The main results are as follows:?1?Calculate and prove the adjacency characteristic polynomial and the Laplacian characteristic polynomial of the generalized subdivision-edge corona graph S?G?!_i?^mH_i,and give the number of spanning trees,the Kirchhoff index and the Laplacian energy like invariant in some special cases,construct infinitely many pairs of A-cospectral and L-cospectral graphs;?2?Calculate and prove the generalized characteristic polynomial of the subdivision-vertex-vertex join graphG₁"G₂ and the subdivision-edge-edge join graph G₁!G₂,get the adjacency characteristic polynomial,Laplacian characteristic polynomial and signless Laplacian characteristic polynomial by generalized characteristic polynomial and give the number of spanning trees,the Kirchhoff index and the Laplacian energy like invariant in some special cases;?3?By the way of computer programming to generate all nonisomorphic graphs at most9 vertices stored by graph6 format and converted this format into adjacency matrix;And then use the Maple software to read the adjacency matrix to calculate the degree matrix,the Laplacian matrix,the signless Laplacian matrix and the adjacency matrix of complement graph;Calculate permanental polynomials of these matrices,compare the permanental polynomials of all nonisomorphic graphs with the same number of vertices and then obtain the number of A-,A&???-,L-and Q-copermanental graphs at most 9 vertices.At last,the cospectral graphs and copermanental graphs are compared and analyzed.We give a conclusion that per-spectrum performs better than the spectrum when we use them to determined graphs.