Main eigenvalues of a graph and its Hamiltonicity

Rok vydání:	2020
Předmět:	Vertex (graph theory) Class (set theory) Polynomial General Mathematics Spectrum (functional analysis) General Physics and Astronomy Circuit rank Hamiltonian path Combinatorics symbols.namesake Computational Theory and Mathematics symbols Adjacency matrix Hamiltonian (quantum mechanics) Mathematics
Zdroj:	Proceedings of the National Academy of Sciences of Belarus. Physics and Mathematics Series. 56:398-407
ISSN:	2524-2415 1561-2430
DOI:	10.29235/1561-2430-2020-56-4-398-407
Popis:	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.
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_________::6c0eac1a087ef4aa03d49c823baa9f6a https://doi.org/10.29235/1561-2430-2020-56-4-398-407 Zobrazit plný text záznamu