Preview

Proceedings of the National Academy of Sciences of Belarus. Physics and Mathematics Series

Proceedings of the National Academy of Sciences of Belarus. Physics and Mathematics Series

Advanced search

Main eigenvalues of a graph and its Hamiltonicity

https://doi.org/10.29235/1561-2430-2020-56-4-398-407

Abstract

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.

About the Author

V. I. Benediktovich
Institute of Mathematics of the National Academy of Sciences of Belarus
Belarus

Vladimir I. Benediktovich – Ph. D. (Physics and Mathematics), Leading Researcher

Surganov Str., 11, 220072, Minsk



References

1. Gantmacher F.R. The Theory of Matrices. Fizmatlit Publ., 2010. 560 p. (in Russian).

2. Cvetković D., Petrić M. A table of connected graphs on six vertices. Discrete Mathematics, 1984, vol. 50, pp. 37–49. https://doi.org/10.1016/0012-365x(84)90033-5

3. Sciriha I., Cardoso D. M. Necessary and sufficient conditions for a Hamiltonian graphs. Journal of Combinatorial Mathematics and Combinatorial Computing, 2012, vol. 80, pp. 127–150.

4. Cardoso D. M. An overview of (κ,τ)-regular sets and their applications. Discrete Applied Mathematics, 2019, vol. 269, pp. 2–10. https://doi.org/10.1016/j.dam.2018.12.020

5. Cardoso D. M., Sciriha I., Zerafa C. Main eigenvalues and (κ,τ)-regular sets. Linear Algebra and its Applications, vol. 432, no. 9, pp. 2399–2408. https://doi.org/10.1016/j.laa.2009.07.039

6. Cvetković D., Rowlinson P., Simić S. Spectral Generalizations of Line Graphs. Cambridge University Press, 2004. https://doi.org/10.1017/cbo9780511751752


Review

Views: 1585

JATS XML


Creative Commons License
This work is licensed under a Creative Commons Attribution 4.0 License.


ISSN 1561-2430 (Print)
ISSN 2524-2415 (Online)