Main eigenvalues of a graph and its Hamiltonicity
| Rok vydání: | 2020 |
|---|---|
| Předmět: | |
| 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: |
|