# Spectral Sufficient Conditions on Pancyclic Graphs

Authors: Guidong Yu; Tao Yu; Xiangwei Xia; Huan Xu
Journal: Complexity
 (2021)

---

## Abstract

A pancyclic graph of ordern is a graph with cycles of all possible lengths from 3 to n. In fact, it is NP-complete that deciding whether a graph is pancyclic. Because the spectrum of graphs is convenient to be calculated, in this study, we try to use the spectral theory of graphs to study this problem and give some sufficient conditions for a graph to be pancyclic in terms of the spectral radius and the signless Laplacian spectral radius of the graph.


---

## Body

## 1. Introduction

LetG=VG,EG be a finite simple undirected graph. Write by n=VG the number of vertex and m=EG the number of edges of the graph G, respectively. Write by δG the minimum degree of G, NGvi the set of neighbours of a vertex vi in G, and di=dGvi=NGvi. If d1,d2,…,dn can be the degree sequence of a graph, d1≤d2≤⋯≤dn, and then, we call it a graphic sequence. Let G and H be two disjoint graphs. Denote by G+H the disjoint union of G and H, which is the graph with the vertex set VG∪VH and edge set EG∪EH. If G1=G2=⋯=Gk, we denote G1+G2+⋯+Gk by kG1. Denote by G∨H the joint of G and H, which is the graph obtained from disjoint union of G and H by adding edges joining every vertex of G to every vertex of H. Denote by Kn−1+v the complete graph on n−1 vertices together with an isolated vertex v and Kn−1−e the complete graph on n−1 vertices deleting the edge. Graph theory is widely used in many fields [1, 2]. Here, we mainly study using the spectral theory of graphs to determine the cycles’ properties of the graph.The adjacency matrix ofG of order n is the matrix AG=aij of order n, where aij=1 if vi is adjacent to vj and aij=0 otherwise. Denote by μG the spectral radius of G, which is the largest eigenvalue of AG. Write by DG the degree diagonal matrix of G. The signless Laplacian matrix of G is defined to be the matrix QG=DG+AG. Denote by qG the signless Laplacian spectral radius of G, which is the largest eigenvalue of QG.A graphG is Hamiltonian (respectively, traceable) if it contains a cycle (respectively, path) containing all vertices of the graph. A cycle of length l is called an l-cycle. A graph G is pancyclic if it contains all l-cycle, 3≤l≤n. Indeed, it is NP-complete that deciding whether a given graph is Hamiltonian.Because the spectrum of graphs is convenient to be calculated, some researchers try to use the spectrum of the graph to character the Hamiltonian of graph. In 2010, Fiedler and Nikiforov [3] first gave sufficient conditions for the given graph to be Hamiltonian (or traceable) in terms of the spectral radius of the graph. In fact, it provides an easy and efficient determination method. And then, many good conclusions have been given [2, 4–14]. But there are no spectral sufficient conditions on pancyclic graphs. In this study, we first give a new sufficient condition for a graph to be pancyclic with the edge number of the graph; then basing on the edge number sufficient condition, we give spectral radius or signless Laplacian spectral radius conditions for a graph to be pancyclic.In this study, we can use some graphs,G1∼G8, in the proof of the theorem, as shown in Figure 1.Figure 1
Some special graphs used in this study. (a)G1. (b) G2. (c) G3. (d) G4. (e) G5. (f) G6. (g) G7. (h) G8.
(a)(b)(c)(d)(e)(f)(g)(h)G1 is the graph obtained from K2∨2K1+Kn−3 by adding two pedending edges on one vertex of degree 2. G2 is the graph obtained from S5 by adding one pedending edge on one vertex of degree 1. G3 is the graph obtained from P3∨4K1 by adding all edges from two vertexes with degree 5 to K1. G4 is the graph obtained from 4K1∨2K1 by adding one pedending edge on one vertex of degree 4. G5 is the graph obtained from K2∨3K1 by adding one pedending edge on two vertexes of degree 4, respectively. G6 is the graph obtained from P3∨3K1 by adding all edges from two vertexes of degree 4 to K1. G7 is the graph obtained from 3K1∨2K1 by adding one pedending edge on one vertex of degree 3. G8 is the graph obtained from K2∨2K1 by adding one pedending edge on two vertexes of degree 3, respectively.


## 2. Preliminary

Given a graphG with n vertex, a vector X∈Rn is called to be defined on G, if there is a 1-1 map φ from VG to the entries of X, simply written Xu=φu.IfX is an eigenvector of AG (or QG), then we call that X is defined on G, and Xu is the entry of X which is corresponded to the vertex u. In fact, when λ is an eigenvalue of G which is corresponded to the eigenvector X,(1)λXv=∑u∈NGvXu,forv∈VG.We call equation (1) is eigen equation of G. When q is a signless Laplacian eigenvalue of G which is corresponded to the eigenvector X, we have(2)q−dGvXv=∑u∈NGvXu,forv∈VG.We call equation (2) is signless Laplacian eigen equation of G.Lemma 1 (see [15]).
LetG be a graph with VG=n, which has degree sequence d1≤⋯≤dn. If for all positive integers k, such that dk≤k<n/2 and dn−k≥n−k, then G is a pancyclic graph or bipartite graph.Lemma 2 (see [16]).
LetG be a connected graph with VG=n. We have(3)μG≤2EG−VG+1,and the equality holds if and only if G=Kn or G=K1,n−1.Lemma 3 (see [2]).
LetG be a graph with VG=n. Then,(4)qG≤2EGVG−1+VG−2.IfG is connected, the equality holds if and only if G=K1,n−1 or G=Kn. Otherwise, the equality holds if and only if G = Kn−1+v.


## 3. Main Results

Theorem 1.
LetG be a simple connected graph, where VG=n≥5, EG=m, δG≥2. If(5)m≥n−22+3,then G is a pancyclic graph, unless G is a bipartite graph or(6)G∈ℕℙ1=K3∨K3+3K1,K4∨K2+4K1,K2∨Kn−4+2K1,2K1∨Kn−4+2K1,K2∨Kn−4−e+2K1,K1∨g1,K1∨K2+Kn−3,K5∨6K1,K3∨K2,6,K4∨K1+K1,5,K3∨K2+3K1,K1∨2K1∨K2+3K1,K2∨K1+K1∨K2+2K1,K2∨G2,K3∨5K1,K4∨5K1,K3∨K1+K1,4,K2∨2K1∨5K1,K3∨2K1+K1,3,K2∨G5,K2∨K1+K2∨4K1,K2∨G4,K1∨5K1∨K2+K1,K2∨G3,5K1∨C4,K3∨4K1,K1,2∨4K1,K2∨K1+K1,3,G6,4K1∨K1+K2,K2∨2K2+K1,K2∨2K1+K1,2,K1∨G7,K1∨G8.Proof.
LetG satisfy the condition of theorem, but it is neither a pancyclic graph nor a bipartite graph. By Lemma 1 and the condition of theorem, there exists an positive integer k, such that dk≤k<n/2 and dn−k≤n−k−1. Then,(7)2m=∑i=1kdi+∑i=k+1n−kdi+∑i=n−k+1ndi≤k2+n−2kn−k−1+kn−1=n2−n+3k2+1−2nk=2n−22+8−k−22n−3k−7.
Thus,(8)m≤n−22+3−12k−22n−3k−7−2.
Becausen−22+3≤m≤n−22+3−1/2k−22n−3k−7−2, k−22n−3k−7−2≤0, i.e., k−22n−3k−7≤2. Next, we discuss in the following four cases.Case 1:k−22n−3k−7=2, i.e., k−2=2 and 2n−3k−7=1 or k−2=1 and 2n−3k−7=2. We can get k=3,n=9 or k=4,n=10.In this time,m=n−22+3, and all inequalities in the above should take mark of equality.Case 1.1:k=3 and n=9. Then, G is a graph with d1=d2=d3=3, d4=d5=d6=5, and d7=d8=d9=8. The three vertices with degree 8 must be adjacent to every vertex, and it induces K3. The three vertices with degree 3 are not adjacent to other vertices, and they induce 3K1. For the rest of 3 vertices with degree 5, in order to make sure the requirement of degree 5, they must be adjacent to each other and induce K3. By the above analysis, G must be isomorphic to K3∨K3+3K1, as given in Table 1.Case 1.2:k=4 and n=10. Then, G is a graph with d1=d2=d3=d4=4, d5=d6=5,andd7=d8=d9=d10=9. The four vertices with degree 9 must be adjacent to every vertex, and they induce K4. The four vertices with degree 4 are not adjacent to other vertices, and they induce 4K1. For the remaining 2 vertices of degree 5, in order to make sure the requirement of the degree 5, they must be adjacent to each other, and they induce K2. By the above analysis, G must be isomorphic to K4∨K2+4K1, as given in Table 1.Case 2:k−22n−3k−7=1, i.e., k−2=1 and 2n−3k−7=1. We cannot find k and n fill the bill.Case 3:k−22n−3k−7=0, i.e., k−2=0 or 2n−3k−7=0.Case 3.1:k−2=0, i.e., k=2. Thus, d2≤2, dn−2≤n−3 and n−2n−3+6≤∑i=1ndi≤n−2n−3+8. Because ∑i=1ndi is even number, thus ∑i=1ndi=n−2n−3+8 or ∑i=1ndi=n−2n−3+6. We can get their graphic sequence and corresponding graphs as given in Table 2.Case 3.2:2n−3k−7=0. Then, n≤13 because k<n/2, and n=11 and k=5 or n=8 and k=3.Case 4:k−22n−3k−7<0, i.e., k≥3 and 2n−3k−7<0. In this case, we have 6≤2k<n≤13.Case 4.1:n=13. We have k≤6, 2n−3k−7>0.Case 4.2:n=12. We have k≤5, 2n−3k−7>0.Case 4.3:n=11. We have k≤5, 2n−3k−7≥0.Case 4.4:n=10. We have k≤4, 2n−3k−7>0.Case 4.5:n=8. We have k≤3, 2n−3k−7=0. The above five cases all contradict to 2n−3k−7<0.Case 4.6:n=9. Then, k≤4. When k=3, then 2n−3k−7=2>0, in contradiction with 2n−3k−7<0.Whenk=4, then 2n−3k−7=−1<0; thus, d4≤4, d5≤4, and we have 48≤∑i=19di≤52 by (5) and (8). Because ∑i=19di is an even number, so ∑i=19di=52 or ∑i=19di=50 or ∑i=19di=48. We can get their graphic sequence and corresponding graphs as given in Table 5.Case 4.7:n=7. Then, k≤3, and because k≥3, i.e., k=3. Thus, d3≤3, d4≤3, and 26≤∑i=17di≤30 by (5) and (8). Because ∑i=17di is an even number, so ∑i=17di=30 or ∑i=17di=28 or ∑i=17di=26. We can get their graphic sequence and corresponding graphs as given in Table 6.
In Tables1–6, we can find the following:(i)
The corresponding graphs of the graphic sequence5,5,5,5,5,5,8,10,10,10,10 contain cycles of every length l, 3≤l≤11(ii)
The corresponding graphs of the graphic sequence4,4,4,4,4,4,8,8,8, 3,4,4,4,4,5,8,8,8, 4,4,4,4,4,6,6,8,8, 4,4,4,4,4,5,7,8,8, and 4,4,4,4,4,6,8,8,8 contain cycles of every length l, 3≤l≤9, respectively(iii)
The corresponding graphs of the graphic sequence3,3,3,4,4,5,7,7 contain cycles of every length l, 3≤l≤8(iv)
The corresponding graphs of the graphic sequence3,3,3,3,4,4,6, 3,3,3,3,3,5,6, and 3,3,3,3,4,6,6 contain cycles of every length l, 3≤l≤7, respectively. Namely, they are the pancyclic graph, a contradiction. The other graphs in Tables 1∼6 are neither pancyclic nor bipartite, and K3∨K3+3K1 and K4∨K2+4K1 are neither pancyclic nor bipartite.
The proof is complete.Table 1
The graphic sequence ofG and its corresponding graph.
Graphic sequenceNonpancyclicn=93,3,3,5,5,5,8,8,8G≅K3∨K3+3K1k=32m=48n=104,4,4,4,5,5,9,9,9,9G≅K4∨K2+4K1k=42m=62Table 2
The graphic sequence ofG and its corresponding graph.
Graphic sequenceNonpancyclicVG=n2,2,n−3,n−3,n−3,…,n−3,n−1,n−1G≅K2∨Kn−4+2K1k=22m=n−2n−3+8VG=n2,2,n−3,n−3,n−3,…,n−3,n−2,n−2G≅2K1∨Kn−4+2K1k=22,2,n−4,n−4,n−3,…,n−3,n−1,n−1G≅K2∨Kn−4−e+2K12m=n−2n−3+82,2,n−4,n−3,n−3,…,n−3,n−2,n−1G≅K1∨G12,2,n−3,n−3,n−3,…,n−3,n−3,n−1G≅K1∨K2+Kn−3Table 3
The graphic sequence ofG and its corresponding graph.
Graphic sequenceNonpancyclicn=115,5,5,5,5,5,10,10,10,10,10G≅K5∨6K1k=52m=80n=115,5,5,5,5,5,9,9,10,10,10G≅K3∨K2,6k=55,5,5,5,5,5,8,10,10,10,10Every graph is pancyclic2m=784,5,5,5,5,5,9,10,10,10,10G≅K4∨K1+K1,5Table 4
The graphic sequence ofG and its corresponding graph.
Graphic sequenceNonpancyclicn=83,3,3,4,4,7,7,7G≅K3∨K2+3K1k=32m=38n=83,3,3,4,4,6,6,7G≅K1∨2K1∨K2+3K12,3,3,4,4,6,7,7G≅K2∨K1+K1∨K2+2K1k=33,3,3,3,4,6,7,7G≅K2∨G23,3,3,4,4,5,7,7Every graph is pancyclic2m=363,3,3,3,3,7,7,7G≅K3∨5K1Table 5
The graphic sequence ofG and its corresponding graph.
Graphic sequenceNonpancyclicn=9(4, 4, 4, 4, 4, 8, 8, 8, 8)G≅K4∨5K1k=42m=52n=9(3, 4, 4, 4, 4, 7, 8, 8, 8)G≅K3∨K1+K1,4k=4(4, 4, 4, 4, 4, 6, 8, 8, 8)Every graph is pancyclic2m=50(4, 4, 4, 4, 4, 7, 7, 8, 8)G≅K2∨2K1∨5K1n=9(4, 4, 4, 4, 4, 4, 8, 8, 8)Every graph is pancyclic(3, 4, 4, 4, 4, 5, 8, 8, 8)Every graph is pancyclic(3, 3, 4, 4, 4, 6, 8, 8, 8)G≅K3∨2K1+K1,3(4, 4, 4, 4, 4, 6, 6, 8, 8)Every graph is pancyclic(3, 3, 4, 4, 4, 7, 7, 8, 8)G≅K2∨G5k=4(2, 4, 4, 4, 4, 7, 7, 8, 8)G≅K2∨K1+K2∨4K1(3, 4, 4, 4, 4, 6, 7, 8, 8)G≅K2∨G4(4, 4, 4, 4, 4, 5, 7, 8, 8)Every graph is pancyclic2m=48(4, 4, 4, 4, 4, 6, 7, 7, 8)G≅K1∨5K1∨K2+K1(3, 4, 4, 4, 4, 7, 7, 7, 8)G≅K1∨G3(4, 4, 4, 4, 4, 7, 7, 7, 7)G≅5K1∨C4Table 6
The graphic sequence ofG and its corresponding graph.
Graphic sequenceNonpancyclicn=73,3,3,3,6,6,6G≅K3∨4K1k=32m=30n=73,3,3,3,5,5,6G≅K1,2∨4K1k=33,3,3,3,4,6,6Every graph is pancyclic2m=282,3,3,3,5,6,6G≅K2∨K1+K1,3n=72,3,3,3,5,5,5G≅G63,3,3,3,4,5,5G≅4K1∨K1+K22,3,3,3,3,6,6G≅K2∨2K2+K1k=32,2,3,3,4,6,6G≅K2∨2K1+K1,23,3,3,3,4,4,6Every graph is pancyclic3,3,3,3,3,5,6Every graph is pancyclic2m=262,3,3,3,4,5,6G≅K1∨G72,2,3,3,5,5,6G≅K1∨G8Theorem 2.
LetG be a simple connected graph, where VG=n≥5, EG=m, δG≥2. If(9)μG≥n2−6n+13,then G is a pancyclic graph, unless G is a bipartite graph or G∈ {K3∨4K1, G6, K2∨3K1}.Proof.
LetG satisfy the condition of theorem, but it is neither a pancyclic graph nor a bipartite graph. Because Kn is pancyclic and δK1,n−1=1, by Lemma 2,(10)n2−6n+13≤μG<2m−n+1,then,(11)m>n−22+3.
By Theorem1, we get G∈ℕℙ1. Because when G∈K3∨K3+3K1,K4∨K2+4K1,(12)m=n−22+3,is a contradiction. So,(13)G∈ℕℙ2=K2∨Kn−4+2K1,2K1∨Kn−4+2K1,K2∨Kn−4−e+2K1,K1∨G1,K1∨K2+Kn−3,K5∨6K1,K3∨K2,6,K4∨K1+K1,5,K3∨K2+3K1,K1∨2K1∨K2+3K1,K2∨K1+K1∨K2+2K1,K2∨G2,K3∨5K1,K4∨5K1,K3∨K1+K1,4,\K2∨2K1∨5K1,K3∨2K1+K1,3,K2∨G5,K2∨K1+K2∨4K1,K2∨G4,K1∨5K1∨K2+K1,K2∨G3,5K1∨C4,K3∨4K1,K1,2∨4K1,K2∨K1+K1,3,G6,4K1∨K1+K2,K2∨2K2+K1,K2∨2K1+K1,2,K1∨G7,K1∨G8.(i)
ForK2∨Kn−4+2K1, by theorem condition, we have n≥5. It is easy to check by WolframAlpha (http://www.wolframalpha.com) that μK2∨Kn−4+2K1 is the largest root of fx=x3+4−nx2−n+1x+4n−20, and f′x=3x2+8−2nx−n−1. The roots of f′x=0 are x1=1/3−n2−5n+19+n−4 and x2=1/3n2−5n+19+n−4. Then by analyzing, when x>x2, we have f′x>0, so fx is monotonically increasing. We can get when n=5, fn2−6n+13<0, and when n≥6, fn2−6n+13>0. Because μG≥n2−6n+13, then n=5, G≅K2∨3K1.(ii)
For2K1∨Kn−4+2K1, by theorem condition, we have n≥5. Using the same method, μ2K1∨Kn−4+2K1 is the largest root of fx=x3+5−nx2+4−2nx+4n−20, and f′x=3x2+10−2nx+4−2n. The roots of f′x=0 are x1=1/3−n2−4n+13+n−5 and x2=1/3n2−4n+13+n−5. Then by analyzing, when x>x2, we have f′x>0, so fx is monotonically increasing. Because when n≥5, we have fn2−6n+13>0; this implies μ2K1∨Kn−4+2K1<n2−6n+13, a contradiction.(iii)
ForK2∨Kn−4−e+2K1, we can get n≥6 from the graph structure. Using the same method, we get μK2∨Kn−4−e+2K1 is the largest root of fx=x4+−n+6x3+9−3nx2+2n−20x+8n−48. Then by analyzing, fn2−6n+13>0, and this implies μK2∨Kn−4−e+2K1<n2−6n+13, a contradiction.(iv)
ForK1∨G1, we can get n≥6 from the graph structure. Using the same method, we get μK1∨G1 is the largest root of fx=x5+6−nx4+9−3nx3+2n−20x2+8n−42x+2n−8. By analyzing, when n≥6, then fn2−6n+13>0, so μK1∨G1<n2−6n+13, a contradiction.(v)
ForK1∨K2+Kn−3, by theorem condition, we have n≥5. Using the same method, we have μK1∨K2+Kn−3 is the largest root of fx=x3+3−nx2−3x+3n−11, and f′x=3x2+6−2nx−3. The roots of f′x=0 are x1=1/3−n2−6n+18+n−3, and x2=1/3n2−6n+18+n−3. Then by analyzing, when x>x2, we have f′x>0, so fx is monotonically increasing. Because when n≥5, we have fn2−6n+13>0; this implies μK1∨K2+Kn−3<n2−6n+13, a contradiction.(vi)
ForG=K2∨2K1∨5K1, let X=X1,X2,…,X9T be the eigenvector corresponding to μG, where Xi1≤i≤5 correspond to the vertex of degree 4, Xi6≤i≤7 correspond to the vertex of degree 7, and Xi8≤i≤9 correspond to the vertex of degree 8. Then, by eigen equation (1), we have(14)X1=X2=⋯=X5,X6=X7,X8=X9,μGX1=2X6+2X8,μGX6=5X1+2X8,μGX8=5X1+2X6+X8.
Transform above into a matrix equationA′G−μGIX′=0, where X′=X1,X6,X8T and(15)A′G=022502521.
Letfx:=detxI−A′G; then, fx=x3−x2−24x−30, and μG is the largest root of fx=0. Through calculation, μG=5.9150<92−6×9+13=6.3246, a contradiction.
Using the same method, we get the spectral radius of the other graphs inℕℙ2, as given inTable 7.
From Table7, all graphs in ℕℙ2 satisfy μG<n2−6n+13, except G∈ {K3∨4K1, G6, K2∨3K1}, a contradiction.
The proof is complete.Table 7
The spectral radius ofG.
GμGn2−6n+13GμGn2−6n+13K1,2∨4K14.21824.4721K4∨5K16.21706.3246K2∨K1+K1,34.37234.4721K3∨4K14.60564.4721K5∨6K17.83108.2462K3∨K2+3K15.17585.3852K3∨K1+K1,46.03226.3246K3∨K2,67.58268.2462K4∨K1+K1,57.67798.2462K1∨2K1∨K2+3K14.81305.3852K2∨K1+K1∨K2+2K14.98375.3852K2∨G24.92735.3852K3∨5K15.00005.3852K2∨G55.83676.3246K2∨K1+K2∨4K15.89046.3246K2∨G45.74076.3246K1∨5K1∨K2+K15.62936.3246K1∨G35.71656.32465K1∨C45.58266.3246K3∨2K1+K1,35.85036.3246G68.27494.47214K1∨K1+K23.84824.4721K2∨2K2+K14.08394.4721K2∨2K1+K1,24.13774.4721K1∨G73.99644.4721K1∨G84.11604.4721Theorem 3.
LetG be a simple connected graph, where VG=n≥5, EG=m, and δG≥2. If(16)qG≥6n−1+2n−6,then G is a pancyclic graph, unless G is a bipartite graph or G∈ {K3∨K1,4+K1,K4∨5K1,K3∨5K1, K3∨4K1,K3∨K2+3K1, K2∨2K1+K1,2, K2∨K1+K1,3,K2∨Kn−4+2K15≤n≤11, K1∨2K2}.Proof.
LetG satisfy the condition of theorem, but it is neither a pancyclic graph nor a bipartite graph. Because Kn is pancyclic and δK1,n−1=1, δKn−1+v=0. By Lemma 3,(17)6n−1+2n−6≤qG<2mn−1+n−2;then,(18)m>n−22+3.
By Theorem1, we get G∈ℕℙ1. Because when G∈K3∨K3+3K1,K4∨K2+4K1,(19)m=n−22+3,a contradiction. So,(20)G∈ℕℙ2=K2∨Kn−4+2K1,2K1∨Kn−4+2K1,K2∨Kn−4−e+2K1,K1∨G1,K1∨K2+Kn−3,K5∨6K1,K3∨K2,6,K4∨K1+K1,5,K3∨K2+3K1,K1∨2K1∨K2+3K1,K2∨K1+K1∨K2+2K1,K2∨G2,K3∨5K1,K4∨5K1,K3∨K1+K1,4,K2∨2K1∨5K1,K3∨2K1+K1,3,K2∨G5,K2∨K1+K2∨4K1,K2∨G4,K1∨5K1∨K2+K1,K2∨G3,5K1∨C4,K3∨4K1,K1,2∨4K1,K2∨K1+K1,3,G6,4K1∨K1+K2,K2∨2K2+K1,K2∨2K1+K1,2,K1∨G7,K1∨G8.(i)
ForK2∨Kn−4+2K1, by the theorem condition, we have n≥5. It is easy to check by Wolfram Alphahttp://www.wolframalpha.com/ that qK2∨Kn−4+2K1 is the largest root of fx=x3+−3n+6x2+2n2−4n−12x−4n2+28n−48. Then, f6/n−1+2n−6=4n4−18n3+90n2−211n+192/n−13. When 5≤n≤11, f6/n−1+2n−6<0, and when n≥12, f6/n−1+2n−6>0. Because qG≥6/n−1+2n−6, then 5≤n≤11, and G=K2∨Kn−4+2K1.(ii)
For2K1∨Kn−4+2K1 because n≥5. Using the same method, we have q2K1∨Kn−4+2K1 is the largest root of fx=x3+−3n+8x2+2n2−8nx−4n2+36n−80. Then, f6/n−1+2n−6=4n−43n3−14n2+34n−41/n−13>0. So, q2K1∨Kn−4+2K1<6/n−1+2n−6, a contradiction.(iii)
ForK2∨Kn−4−e+2K1 because n≥6. Using the same method, we get qK2∨Kn−4−e+2K1 is the largest root of fx=x4+−4n+12x3+5n2−28n+28x2+−2n3+12n2+12n−120x+4n3−52n2+224n−320. Then, f6/n−1+2n−6>0. So, qK2∨Kn−4−e+2K1<6/n−1+2n−6, a contradiction.(iv)
ForK1∨G1, we can get n≥6. Using the same method, we get qK1∨G1 is the largest root of fx=x5+−5n+14x4+9n2−48n+54x3+−7n3+50n2−78n−42x2+2n4−12n3−36n2+346n−544x−4n4+60n3−332n2+796n−688. Then, f6/n−1+2n−6=43n8−54n7+437n6−2150n5+7066n4−16131n3+25286n2−25525n+13012/n−15. We can find that when n≥6, f6/n−1+2n−6 is monotone increasing because f6/n−1+2n−6|n=6>0; thus, qK1∨G1<6/n−1+2n−6, a contradiction.(v)
ForK1∨K2+Kn−3, by theorem condition, n≥5. Using the same method, qK1∨K2+Kn−3 is the largest root of fx=x3+5−3nx2+2n2−n−16x−6n2+34n−44. The roots of fx=0 are x1=1/2−4n2−36n+97+2n−3, x2=n−2, and x3=1/24n2−36n+97+2n−3<6/n−1+2n−6, when n≥6. So, qK1∨K2+Kn−3<6/n−1+2n−6(n≥6); when n=5, qK1∨K2+Kn−3>6/n−1+2n−6; and when n≥6, qK1∨K2+Kn−3<6/n−1+2n−6(n≥6). Because qG≥6/n−1+2n−6, then n=5, and G=K1∨K2+Kn−3=K1∨2K2.(vi)
ForK2∨2K1∨5K1, let X=X1,X2,…,X9T be the eigenvector corresponding to qG, where Xi1≤i≤5 correspond to the vertex of degree 4, Xi6≤i≤7 correspond to the vertex of degree 7, and Xi8≤i≤9 correspond to the vertex of degree 8. Then, by signless Laplacian eigen equation (2), we have(21)X1=X2=⋯=X5,X6=X7,X8=X9,qG−4X1=2X6+2X8,qG−7X6=5X1+2X8,qG−8X8=5X1+2X6+X8.
Transform above into a matrix equationQ′G−qGIX˜=0, where X˜=X1,X6,X8T and(22)Q′G=422572529.
Letgx:=detxI−Q′G, then gx=x3−20x2+103x−116, and qG is the largest root of gx=0. Through calculation, qG=12.5052<6/9−1+2×9−6=12.7500. Using the same method, we get the signless Laplacian spectral radius of the other graphs in ℕℙ2, as given in Table 8.
From Table8, all graphs in ℕℙ2 except G∈ {K3∨K1,4+K1,K4∨5K1,K3∨5K1, K3∨4K1,K3∨K2+3K1, K2∨2K1+K1,2, K2∨K1+K1,3}, other graphs satisfy qG<10/n−1+2n−6, a contradiction.
The proof is complete.Table 8
The signless Laplacian spectral radius ofG.
GqG6/n−1+2n−6GqG6/n−1+2n−6K1,2∨4K18.89659.0000K4∨5K113.178912.7500K2∨K1+K1,39.34089.0000K3∨4K19.77209.0000K5∨6K116.588716.6000K3∨K2+3K111.095910.8571K3∨K1+K1,412.838112.7500K3∨K2,616.035216.6000K4∨K1+K1,516.306216.6000K1∨2K1∨K2+3K110.237210.8571K2∨K1+K1∨K2+2K110.711610.8571K2∨G210.639310.8571K3∨5K110.899010.8571K2∨G512.466112.7500K2∨K1+K2∨4K112.530312.7500K2∨G412.238612.7500K1∨5K1∨K2+K111.878712.7500K1∨G312.091412.75005K1∨C411.623512.7500K3∨2K1+K1,312.560112.7500G68.27499.00004K1∨K1+K28.00009.0000K2∨2K2+K18.91649.0000K2∨2K1+K1,29.00009.0000K1∨G78.56509.0000K1∨G88.84059.0000


## 4. Conclusions

There are many researchers who studied the spectral theory of graphs in the Hamiltonian graph, but few considered the spectral sufficient conditions on pancyclic graphs. In this study, in terms of the edge number, the spectral radius, and the signless Laplacian spectral radius of the graph, three theorems are established for a graph to be pancyclic. The proofs are also given accordingly.



---

*Source: 3630245-2021-07-15.xml*