Hamiltonian graphs of given order and minimum algebraic connectivity

Abstract

In this paper, we study the algebraic connectivity of a Hamiltonian graph, and determine all Hamiltonian graphs whose algebraic connectivity attain the minimum among all Hamiltonian graphs on n vertices.

Keywords:

• Algebraic connectivity
• Hamiltonian graph
• lower bound

Acknowledgements

We are grateful to the anonymous referees for their valuable suggestions and corrections which result in an improvement of the original manuscript.

Notes

No potential conflict of interest was reported by the authors.

Additional information

Funding

This work was supported by the National Natural Science Foundation of China [grant number 11171290], [grant number 11271315]; the Natural Science Foundation of Jiangsu Province [grant number BK20151295].