The Hamiltonian Properties,?-deficiency And Supereulerianicity Of Graphs

Graph Theory is an important branch of mathematics,which has a wide range of applications in many fields such as transportation,computer science and information technology,communication and network technology and so on.The Hamilton circuit problem is one of the famous problems in graph theory,which has attracted the scholars' attention all over the world.With respect to Hamiltonian problems,many known sufficient conditions mainly include two important types.The first one is based on the parameters such as independence number,minimum degree,degree sequence and so on.The second one is based on some specific forbidden subgraphs in structural graph theory.In the study of parameters,most of the early work is based on edge number condition,degree condition and neighborhood condition to characterize the Hamiltonian properties of graphs.In 2010,Fiedler and Nikiforov first presented the relationship between spectral radius and Hamiltonian properties of graphs,and established the relationship between spectral theory of graph and Hamiltonian properties.The spectral theory of graph mainly uses algebraic theory and methods,combined with graph theory and combinatorics theories,to study the relationship between the eigenvalues of the matrix and other invariants of the graph,it is an important research topic of contemporary graph theory,combinatorial matrix and algebraic combination,and has been widely used in quantum mechanics,theoretical physics,chemistry and so on.The establishment of the relationship between the spectral theory of graph and Hamiltonian properties has been widely concerned and studied by researchers.In recent years,there have been a great number of research achievements on characterization of Hamiltonian properties and other structural properties by spectral conditions.This thesis studies the Hamiltonian properties,?-deficiency and supereulerianicity of graphs.The main results are as follows:1)We get several sufficient conditions for a graph to have a Hamiltonian property.First,we use eigenvector theory,Rayleigh quotient and inequality theory to improve a result of Nikiforov in 2016 and to obtain a lower bound condition of spectral radius for a balanced bipartite graph with given order and minimum degree to be traceable.Then by using Erdos' idea of taking the minimum degree as a parameter,we obtain a new edge number condition for a graph with a given order and minimum degree to be Hamilton-connected.Finally,we get one spectral sufficient conditions for a graph with a given order and minimum degree to be Hamilton-connected by using the edge number condition,eigenvector theory,Kelmans transform,Rayleigh quotient and inequality theory.2)We give several sufficient conditions for a graph to be ?-deficient.The deficiency of a graph G,denoted by def(G),is the number of vertices unmatched by a maximum matching in G.Let ? be a nonnegative integer,G is called ?-deficient if def(G)??.In this thesis,we obtain a Chvatal-Erdos type independence number condition for a graph to be ?-deficient by using Fan Lemma,Berge maximum matching theorem and Kouder theorem.Furthermore,we obtain a minimum degree condition,a degree sum condition and a degree sequence condition for a graph to be ?-deficient by using the methods accumulated in the study of Hamiltonian properties.Finally,some best possible spectral sufficient conditions are obtained by using the above Chvatal-Erdos type independence number condition and the minimum degree condition.3)We obtain several sufficient conditions for a graph to be supereulerian.In 1991,Catlin and Chen gave a edge number condition for 2-edge connected graphs and 3-edge connected graphs to be supereulerian by using the Catlin reduction method,respectively.In this thesis,we improve the above two edge number conditions by utilizing the idea that take the minimum degree as a new parameter for studying Hamiltonian properties,Catlin reduction method and the thought of extremal graph theory.Then by using the above edge number condition that we get and Fourier-Budan theorem,as well as the methods accumulated in the study of spectral conditions for Hamiltonian properties,we obtain several spectral sufficient conditions involving adjacency spectral radius and signless laplacian spectral radius for a graph to be supereulerian.