Research On The Algebraic Conditions Of Hamiltonicity Of Graphs And Related Problems

The Hamilton problem is a very classical problem in graph theory,also one of famous NP-complete problems.Most of previous results studied sufficient conditions for the existence of Hamilton cycle(or path)in the graph based on the structural properties of the graph.In 2010,Fiedler and Nikiforov gave sufficient conditions on adjacent spectral radius for the existence of Hamilton cycle(or path)of graphs.Then using spectra radius,Wiener index and Harary index to give sufficient conditions for the existence of Hamilton cycles(or paths)has become a hot research topic for domestic and foreign scholars.This thesis focuses on studying hamiltonian properties of graphs,including hamiltonicity,traceability,Hamilton-connectivity and so on,by using conditions on spectral radius,Wiener index and so on.It has important theoretical significance and application value.The main research results of this paper are as follows:1.We study the hamiltonicity and traceability of graphs on spectral conditions.By using Chvátal’s degree sequence condition,and combining with the relationship between spectral radius and edge number of graphs,we give some sufficient conditions in terms of adjacent spectral radius and signless Laplacian spectral radius for graphs satisfyingδ(G)≥ k to be hamiltonian.We characterize all exceptional graphs,i.e.,graphs satisfying the condition but not hamiltonian,by Bondy and Chvátal’s closure;Furthermore,by using the relationship of independence number and connectivity of hamiltonian graphs proposed by Chvátal and Erd(?)s,we give sufficient conditions on adjacent spectral radius for k-connected graphs to be hamiltonian or traceable,which depends only on the order and connectivity of the graph.2.We study the Hamilton-connectivity of graphs on spectral conditions.Under the condition of minimum degree δ(G)≥ 3,by analysing degree sequence,we give some sufficient conditions on adjacent spectral radius and signless Laplacian spectral radius for graphs to be Hamilton-connected.Then,by imposing minimum degree conditionδ(G)≥ k and using Rayleigh’s principle,we give the sufficient condition for graphs to be Hamilton-connected in terms of signless Laplacian spectral radius.Furthermore,we characterize all exceptional graphs by using quotient matrix and Fourier-Budan theorem.At last,by using the relationship between independence number and connectivity for Hamilton-connected graphs proposed by Chvátal,we give the sufficient condition for kconnected graphs to be Hamilton-connected on adjacent spectral radius,which depends only on the order and connectivity of the graph.3.We study other hamiltonian properties on Wiener index,Harary index and Wiener-type invariants conditions.By using the relationship between Wiener and Harary indices and the edge number,we give sufficient conditions on Wiener index and Harary index of the graph and its complement for the graph to be Hamilton-connected or traceable from every vertex.Furthermore,by using degree sequence conditions for Hamiltonconnected graphs,k-Hamilton graphs,k-edge-Hamilton graphs and k-path-coverable graphs,we give sufficient conditions on Wiener-type invariants for these graphs,which are more general.