The Spectral Characterization of Hamiltonicity of Graphs Volume 5 - Issue 2

Guidong Yu^1,2* and Gaixiang Cai¹

• ¹School of Mathmatics and Physic, Anqing Normal University, China
• ²Department of Public Teanching, Hefei Preschool Education College, China

Received:September 13, 2021   Published: September 29, 2021

Corresponding author: Guidong Yu, School of Mathmatics and Physic, Anqing Normal University, Anqing 246133, Department of Public Teanching, Hefei Preschool Education College, Hefei 230013, China

DOI: 10.32474/JAAS.2021.05.000209

Abstract PDF

It is an important NP-complete problem in structure graph theory to judge whether a graph is Hamiltonian. So far, there is no perfect description on this problem. Therefore, it has always been concerned by the workers of graph theory and mathematics. It is explored that the new method for characterization of Hamiltonicity of graphs. Because the spectrum of a graph can well reflect the structural properties of a graph and is easy to calculate, at the 2010 conference of the theory of graph spectra, M. Fiedler and V. Nikiforov formally proposed whether the theory of graph spectra can be used to study the Hamiltonicity of a graph, and they [1] gave sufficient conditions for given graph to be Hamiltonian (or traceable) in terms of the spectral radius of the graph. Since then, relying on the spectrum of matrix representation of graph, giving the spectral sufficient conditions of the Hamiltonian graph has been a new method to study the Hamilton problem. Many results have been obtained by using the spectral radius and the signless Laplacian spectral radius of the graph to describe the Hamiltonicity of the graph. [2] firstly gave a sufficient condition for a graph G to be Hamiltonian and traceable by using the signless Laplacian spectral radius of the complement of the graph [3] optimized the condition of the number of edges of the Hamilton graph, gave a better condition for G to be traceable by using the spectral radius of the graph G, and firstly gave a sufficient condition for the balanced bipartite graph to contain the Hamilton cycle by the spectral radius of its quasi-complement graph. [4] firstly used the spectral radius and signless Laplacian spectral radius of the graph to describe the Hamilton-connected of the graph. [5] used the signless Laplacian spectral radius of the quasi-complement graph of the balanced bipartite graph to give a sufficient condition for the balanced bipartite graph to be Hamiltonian and used the signless Laplacian spectral radius of the graph G to give a sufficient condition for the graph G to be traceable or Hamilton-connected. [6] continued to study the relationship between the Hamiltonicity and spectral radius of general graphs and balanced bipartite graphs and extended the conclusions in [3] and [5]. [7] firstly proposed to use the stability of graphs to study the Hamiltonian properties of graphs, and also summarized the method of studying the spectral characterization of the Hamiltonian graph by optimizing the boundary conditions of the Hamiltonian graph. [8] firstly characterized traceability of connected claw-free graphs by spectral radius. [9] discussed spectral conditions for Hamiltonicity of claw-free graphs. [10] firstly presented spectral sufficient conditions for a k-connected graph to be traceable or Hamilton-connected. [11] firstly presented sufficient conditions based on spectral radius for a graph to be k-connected, k-edge- connected, k-Hamiltonian, k-edge-Hamiltonian, β-deficient and k-path-coverable. Lately, [12] firstly gave spectral radius or signless Laplacian spectral radius conditions for a graph to be pancyclic.

Because the minimum degree of a graph is related to the density of the graph, with the deepening of research, people began to study the spectral characterization of Hamiltonian properties of graphs with large minimum degree conditions and gave the better conclusions. By adding the condition of large minimum degree, [13] firstly presented some (signless Laplacian) spectral radius conditions for a simple graph and a balanced bipartite graph to be traceable and Hamiltonian, respectively. Subsequently, [14] optimized the lower bound of the spectral condition of simple graphs with large minimum degree; [15] optimized the lower bound of the spectral condition of balanced bipartite graphs with large minimum degree. [16] characterized the signless Laplacian spectral radius conditions for a graph or balanced bipartite graph with large minimum degree to be Hamiltonian. [17] and [18] studied the signless Laplacian spectral radius condition for a graph with large minimum degree to be Hamilton-connected. [19] presented some spectral radius conditions for a balanced bipartite graph or a nearly balanced bipartite graph with large minimum degree to be traceable, respectively. [20] gave some spectral sufficient conditions for a balanced bipartite graph with large minimum degree to be traceable and Hamiltonian in terms of the spectral radius of the graph with large minimum degree. It strengthened the according results of Li and Ning for n sufficiently large. [21] presented some conditions for a simple graph with large minimum degree to be Hamilton-connected and traceable from every vertex in terms of the spectral radius of the graph or its complement respectively and gave better conditions for a nearly balanced bipartite graph with large minimum degree to be traceable in terms of spectral radius, signless Laplacian spectral radius of the graph or its quasi-complement respectively. [22] presented sufficient spectral conditions of a connected graph with large minimum degree to be k-hamiltonian or k-path-coverable or β-deficient, for relatively large n. [23] gave the sufficient conditions for a graph with large minimum degree to be s-connected, s-edge-connected, β-deficient, s-path-coverable, s-Hamiltonian and s-edge-Hamiltonian in terms of spectral radius of its complement.

Other spectral characterizations on Hamiltonicity, at present, only [24,25] used the Laplacian eigenvalues to give the spectral sufficient condition for the graph to be Hamiltonian. [26] firstly applied the distance signless Laplacian spectral radius of the graph’s complement to give a sufficient condition for the graph to be traceable or Hamiltonian. [27] firstly discussed the Hamiltonian in terms of the energy of graph. [28], by adding the maximum degree condition on the basis of [26], used the energy of complement graph to give the sufficient conditions for the graph to be traceable, Hamiltonian and Hamilton-connected. The results optimized the conclusions of [26] in a sense. [22] gave some sufficient conditions for a nearly balanced bipartite graph with large minimum degree to be traceable in terms of the energy, the first Zagreb index and the second Zagreb index of the quasi-complement of the graph, respectively. By observing, we find that the conditions of all the above conclusions deduce that the graphs are dense. In fact, there are many Hamiltonian graphs with non dense edge distribution, such as cycles. Therefore, it is necessary to study whether a nondense graph (sparse graph) is a Hamiltonian graph, but there are few research results. Komlos and Szemeredi proposed that almost all graphs are Hamiltonian graphs in 1975. Inspired by this, [29] characterized the Hamiltonian property of regular graphs by using the adjacency spectrum of graphs; [30] characterized the Hamiltonian property of almost regular graphs by using the Laplace spectrum of graphs. In 2011, Radcliffe proposed whether we can give sufficient conditions for Hamiltonian graphs by using the normal Laplace spectrum of graphs. In 2012, [31] studied this problem, gave corresponding conclusions, and explained that the conclusions are applicable to the determination of Hamiltonicity of general graphs.

Although there are a lot of results, there are still many problems worthy of further study. Firstly, combining the ideas from theorems of Ore and Fan to develop extremal spectral conditions for dense graphs (with given connectivity, toughness, forbidden subgraphs) to be Hamiltonian (or related structural properties). Such as, finding spectral sufficient conditions for a graph or its complement to be Hamilton-connected, or k-Hamiltonian, k-path-coverable, k-edge-Hamiltonian; signless Laplacian spectral radius sufficient conditions for a (nearly) balanced bipartite graph or its nearly complement to be traceable, or Hamiltonian; (signless Laplacian) spectral radius sufficient conditions for the nearly complement of a balanced bipartite graph to be bipancyclic or considering the case with minimum degree; the characterization of Hamiltonicity of graphs with 1-tough [32,33]. Secondly, due to the difficulty of research, there are only three papers to study Hamiltonian properties of sparse graphs, but there are many sparse Hamiltonian graphs. Therefore, there is a lot of space to explore some sufficient or necessary conditions for sparse graphs with some properties to be Hamiltonian (or related structural properties) by using the spectrum of the graph and corresponding eigenvector. At last, directed graphs also have Hamiltonian properties, but all previous studies have only considered undirected graph. So, it is also very valuable to study extremal spectral conditions for oriented graphs to be Hamiltonian. The research on the spectral characterization of Hamiltonicity of graphs build a bridge between structure graph theory and algebraic graph theory. Expected results not only enrich the study of Hamilton problem in structural graph theory, but also extend the spectral study of algebraic graph theory, thus promoting the research of algebraic method of Hamilton problem.

Supported by the Natural Science Foundation of China (No. 11871077), the NSF of Anhui Province (No. 1808085MA04), the NSF of Department of Education of Anhui Province (No. KJ2020A0894), and Research and innovation team of Hefei Preschool Education College (No. KCTD202001).

1. M Fiedler, V Nikiforov (2010) Spectral radius and Hamiltonicity of graphs. Linear Algebra and its Applications 432(9): 2170-2173.
2. Bo Zhou (2010) Signless Laplacian spectral radius and Hamiltonicity. Linear Algebra and its Applications 432(2-3): 566-570.
3. Mei Lu, Huiqing Liu, Feng Tian (2012) Spectral Radius and Hamiltonion graphs. Linear Algebra and its Applications 437(7): 1670-1674.
4. Guidong Yu, Yizheng Fan (2013) Spectral conditions for a graph to be Hamilton-connected. Applied Mechanics and Materials 336-338: 2329-2334.
5. Guidong Yu, Miaolin Ye, Gaixiang Cai, Jinde Cao (2014) Signless Laplacian Spectral Conditions for Hamiltonicity of Graphs. Journal of Applied Mathematics 2014(15): 1-6.
6. Ruifang Liu, Wai Chee Shiu, Jie Xue (2015) Sufficient spectral conditions on Hamiltonian and trace- able graphs. Linear Algebra and its Applications 467: 254-266.
7. Rao Li (2014) Laplacian spectral radius and some Hamiltonian properties of graphs. Applied Math- ematics E-Notes 14(2014): 216-220.
8. Bo Ning, Binlong Li (2015) Spectral radius and traceability of connected claw-free graphs. Mathe- matics 2015(2): 1-8.
9. Binlong Li, Bo Ning (2015) Spectral conditions for Hamiltonicity of claw-free graphs. arXiv 1504: 4195.
10. Guidong Yu, Rao Li, Baohua Xing (2015) Spectral Invariants and Some Stable Properties of a Graph. Ars Combinatoria 121: 33-46.
11. Lihua Feng, Weijun Liu, Minmin Liu, Pengli Zhang (2017) Spectral conditions for graphs to be k- Hamiltonian or k-path-coverable. Discussiones Mathematicae Graph Theory 40(1): 1-15.
12. Guidong Yu, Tao Yu, Xiangwei Xia, Huan Xu (2021) Spectral Sufficient Conditions on Pancyclic Graphs. Complexity 2021: 1-8.
13. Binlong Li, Bo Ning (2016) Spectral analogues of Erd˝os’ and Moon-Moser’s theorems on Hamilton cycles. Linear and Multilinear Algebra 64(11): 1-18.
14. V Nikiforov (2016) Spectral radius and Hamiltonicity of graphs with large minimum degree. Czechoslovak Mathematical Journal 66(3): 925-940.
15. Jun Ge, Bo Ning (2016) Spectral radius and Hamiltonicity of graphs with large minimum degree, arXiv: 1606. 08530.
16. Yawen Li, Yao Liu, Xing Peng (2018) Signless Laplacian spectral radius and Hamiltonicity of graphs with large minimum degree. Linear and Multilinear Algebra 66(10): 2011-2023.
17. Mingzhu Chen, Xiaodong Zhang (2018) The number of edges, spectral radius and Hamilton- connectedness of graphs. Journal of Combinatorial Optimization 35(4): 1104-1127.
18. Qiannan Zhou, Ligong Wang, Yong Lu (2020) Signless Laplacian spectral conditions for Hamilton- connected graphs with large minimum degree. Linear Algebra and its Applications 592: 48-64.
19. Binlong Li, Bo Ning (2017) Spectral analogues of Moon-Mosers theorem on Hamilton paths in bi- partite graphs. Linear Algebra Appl 515: 180-195.
20. Guisheng Jiang, Lifang Ren, Guidong Yu (2019) Sufficient Conditions for Hamiltonicity of Graphs with Respect to Wiener Index, Hyper-Wiener Index, and Harary Index. Journal of Chemistry 2019: 1-9.
21. Guidong Yu, Yi Fang, Yizheng Fan, Gaixiang Cai (2019) Spectral radius and Hamiltonicity of graphs. Discussiones Mathematicae Graph Theory 39(2019): 951-974.
22. Lihua Feng, Pengli Zhang, Henry Liu, Weijun Liu, Minmin Liu, Yuqin Hu, et al (2017) Spectral conditions for some graphical properties. Linear Algebra and its Applications 524(1): 182-198.
23. Guidong Yu, Yi Xu, Guisheng Jiang (2019) Energy and the Zagreb index conditions for nearly balanced bipartite graphs to be traceable. Journal of combinatorial Mathematics and Combi-natorial Computing 110: 109-123.
24. Rao Li (2012) Egienvalues, Laplacian eigenvalues and some Hamiltonian properties of graphs, Utilitas Mathematica 88: 247-257.
25. Rao Li (2014) Spectral conditions for some stable properties of graphs, Journal of Combinatorial Mathematics and Combinatorial Computing 88: 199-205.
26. Qiannan Zhou, Ligong Wang (2016) Distance signless Laplacian spectral radius and Hamiltonian properties of graphs. Linear Multilinear Algebra 65(11): 2316-2323.
27. Rao Li (2009) Energy and Some Hamiltonian Properties of Graphs, Applied Mathematical Sciences 3(56): 2775-2780.
28. Guidong Yu, Gaixiang Cai, Mioalin Ye, Jinde Cao (2014) Energy conditions for Hamiltonicity of graphs. Discrete Dynamics in Nature and Society 2014: 1-6.
29. M Krivelevich, B. Sudakov (2003) Sparse pseudo-random graphs are Hamiltonian. Journal of Graph Theory 42(2003): 17-33.
30. S Butler, F Chung (2010) Small spectral gap in the combinatorial Laplacian implies Hamiltonian. Annals of Combinatorics 13: 403-412.
31. Yizheng Fan, Guidong Yu (2012) Spectral condition for a graph to be Hamiltonian with respect to Normalized Laplacian.
32. Weijun Liu, Minmin Liu, Lihua Feng (2017) Spectral conditions for graphs to β-deficient involving minimum degree. Linear Multilinear Algebra 66(4): 1-11.
33. Guidong Yu, Yi Fang, Yi Xu (2017) Spectral condition of complement for some graphical properties. Journal of combinatorial Mathematics and Combinatorial Computing 108 (2019): 65C74.