Open AccessMain eigenvalues of a graph and its Hamiltonicity
Author(s) -
В. И. Бенедиктович
Publication year - 2020
Publication title -
vescì nacyânalʹnaj akadèmìì navuk belarusì. seryâ fìzìka-matèmatyčnyh navuk
Language(s) - English
Resource type - Journals
eISSN - 2524-2415
pISSN - 1561-2430
DOI - 10.29235/1561-2430-2020-56-4-398-407
Subject(s) - mathematics , combinatorics , regular graph , discrete mathematics , line graph , strongly regular graph , symmetric graph , voltage graph , graph , pathwidth
The concept of (κ,τ)-regular vertex set appeared in 2004. It was proved that the existence of many classical combinatorial structures in a graph like perfect matchings, Hamiltonian cycles, effective dominating sets, etc., can be characterized by (κ,τ)-regular sets the definition whereof is equivalent to the determination of these classical combinatorial structures. On the other hand, the determination of (κ,τ)-regular sets is closely related to the properties of the main spectrum of a graph. This paper generalizes the well-known properties of (κ,κ)-regular sets of a graph to arbitrary (κ,τ)-regular sets of graphs with an emphasis on their connection with classical combinatorial structures. We also present a recognition algorithm for the Hamiltonicity of the graph that becomes polynomial in some classes of graphs, for example, in the class of graphs with a fixed cyclomatic number.