Some spectral sufficient conditions for a graph being pancyclic

1.   Introduction

In this paper, we use $G = (V(G), E(G))$ to denote a graph with the vertex set $V(G) = \left\{v_1, v_2, \cdots , v_n\right\}$ and the edge set $E(G)$. Let $e(G) = m = |E(G)|$ be the number of edges of the graph $G$. For any $v_i\in\ V(G)$, $d_i = d_{v_i} = d_{G}(v_{i})$ represents the degree of $v_i$. Let $(d_1, d_2, \cdots , d_n)$ be the degree sequence of $G$, where $d_1 \leq d_2 \leq \cdots \leq d_n$. Let $\delta$ or $\delta(G)$ be the minimum degree of $G$, and $N_G(v)$ be the set of neighbors of a vertex $v$ in $G$. The complete graph of order $n$ is denoted by $K_n$, and the complete bipartite graph with the partite sets $X$ and $Y$ with $|X| = m$ and $|Y| = n$ is denoted by $K_{m, n}$. The disjoint union of $G$ and $H$, denoted by $G+H$, is the graph with vertex set $V(G)\cup V(H)$ and edge set $E(G)\cup (H)$. In particular, if $G_1 = G_2 = \cdots = G_k$, then let $kG_1 = G_1+G_2+\cdots +G_k$. Similarly, we use $G\vee H$ to denote the join of $G$ and $H$. The complete graph on $n-1$ vertices together with an isolated vertex $v$ is denoted by $K_{n-1}+v$.

Let $A(G) = [a_{ij}]$ be the adjacency matrix of $G$, where $a_{ij} = 1$ if $v_i$ is adjacent to $v_j$, $a_{ij} = 0$ otherwise. We use $\mu(G)$ to denote the maximum eigenvalue of $A(G)$, which is called the spectral radius of $G$. Let $D(G)$ be the diagonal degree matrix of $G$, and $Q(G) = D(G)+A(G)$ be the signless Laplacian matrix of $G$. Let $q(G)$ be the maximum eigenvalue of $Q(G)$, which is called the signless Laplacian spectral radius.

We call the cycle (path) containing all vertices of $G$ the Hamilton cycle (path) of $G$. If graph $G$ contains a Hamiltonian cycle (path), then $G$ is a Hamiltonian traceable graph. If for any positive integer $k(3\leq k\leq n)$, $G$ contains a cycle of length $k$, then $G$ is called a pancyclic graph. Obviously, a bipartite graph is not a pancyclic graph. In addition, a Hamilton cycle graph is certainly Hamiltonian, but the converse is incorrect. Determining whether a given graph is a Hamilton graph or not is one of the most difficult classical problems in graph theory. In fact, it is an $NP-$complete problem.

In recent years, more and more worldwide researchers use the spectral theory of graphs to solve this problem. First, Fiedler and Nikiforov ^[1] established a sufficient condition on spectral radius for the existence of a graph with Hamilton paths and Hamilton cycles. Yu and Fan ^[2] used the spectral radius of the adjacency matrix or signless Laplacian matrix of the graph or its complement to give a sufficient condition for the graph to be Hamilton-connected. Lu et al. ^[3] gave the spectral sufficient conditions for a bipartite graph to be a Hamilton graph. Many scholars have studied similar problems under different spectral conditions since that time, see ^{[4,5,6,7,8,9,10]}. Recently, Yu et al. ^[11] has discussed for the first time the spectral sufficient conditions for a graph with a minimum degree $\delta(G)\geq2$ to be a pancyclic graph. In this paper, a new edge sufficient condition for a graph with a minimum degree $\delta(G)\geq3$ to be a pancyclic graph is established by using a similar method. Then, a sufficient condition on (signless Laplacian) spectral radius of a graph to be a pancyclic graph is given based on the edge sufficient condition.

2.   Preliminary

Given a graph $G$ with order $n$, a vector $X\in R^n,$ is called to be defined on $G$, if there is a 1-1 mapping $\varphi$ from $V(G)$ to vector, simply written $X_u = \varphi(u)$.

$X$ is defined on $G$ if $X$ is the eigenvector of $A(G)(Q(G))$. Let $X_u$ denote the term of $X$ corresponding to vertex $u$. One can find that when $\lambda$ is an eigenvalue of $G$ corresponding to the eigenvector, $X$ if and only if $X\not = 0$,

The equation above is the eigen-equation of $G$. One can find when $q$ is an signless Laplacian eigenvalue of $G$ corresponding to the eigenvector $X$ if and only if $X\not = 0$,

The equation above is the $signless$ $Laplacian$ eigen-equation of $G$.

Lemma 2.1 ^[12] Let $G$ be a graph with $n$ vertices, and its degree sequence is $d_1\leq d_2\leq \cdots \leq d_n$. $G$ is a pancyclic graph or bipartite graph if for all positive integers $k$ there is always $d_{n-k}\geq n-k$ and $d_k\leq k < n/2$.

Lemma 2.2 ^[13] Let $G$ be a graph with $n$ vertices and $m$ edges, then

and the equality holds if and only if $G = K_n$ or $G = K_{1, n-1}$.

Lemma 2.3 ^[14] Let $G$ be a graph with $n$ vertices and $m$ edges, then

and the equal sign is true if and only if $G = K_n$ or $G = K_{1, n-1}$ when $G$ is connected. If $G$ is not connected, the equal sign is true if and only if $G = K_{n-1}+v$.

Lemma 2.4 ^[15] Let $G$ be a Hamiltonian graph and satisfy $e(G)\geq n^2/4$, then $G$ is either a complete bipartite graph $K_{\frac{n}{2}, \frac{n}{2}}$ (where $n$ is even), or a pancyclic graph.

Lemma 2.5 ^[16] If a Hamiltonian graph $G$ of order $n$ satisfies

then $G$ is a pancyclic graph or $G$ is a bipartite graph.

3.   Main results

Theorem 3.1 Let $G$ be a connected graph with $n(n\geq5)$ vertices and $m$ edges, and its minimum degree $\delta(G)\geq3$. If

then $G$ is a pancyclic graph or a bipartite graph or $G\in NP_1 = \{(3K_1+K_{n-6})\vee K_3$, $(4K_1+K_3)\vee K_4$, $(6K_1+K_2)\vee K_6$, $9K_1\vee K_8$, $8K_1\vee K_7$, $(K_1+K_{1, 7})\vee K_6$, $K_{2, 8}\vee K_5$, $K_6\vee (2K_1+K_{1, 6})$, $K_4\vee 2K_1\vee (K_2+K_{1, 6})$, $K_5\vee (K_1+K_{1, 6})$, $(K_2+K_{1, 5})\vee K_5$, $(2K_1\vee K_4)\vee 7K_1$, $(K_1+K_2+K_{1, 4})\vee K_5$, $(2K_1+K_{1, 5})\vee K_5$, $(K_1+K_2\vee 6K_1)\vee K_4$, $(K_{1, 5}+K_2)\vee 2K_1\vee K_3$, $7K_1\vee K_6$, $K_5\vee (2K_1+K_{1, 3}+K_2)$, $K_4\vee [K_1+K_1\vee (K_{1, 4}+K_2)]$, $K_4\vee (K_1+2K_1\vee 6K_1)$, $K_3\vee K_{3, 7}$, $K_5\vee (3K_1+K_{1, 4})$, $K_3\vee 2K_1\vee (K_1+K_{1, 4}+K_2)$, $K_4\vee [K_1\vee (K_1+K_{1, 5})+K_1]$, $K_3\vee 2K_1\vee (2K_1+K_{1, 5})$, $(5K_1+K_2)\vee K_5$, $K_4\vee (K_1\vee (4K_1+K_2)+K_1)$, $7K_1\vee K_5$, $(5K_1+K_2)\vee 2K_1\vee K_3$, $6K_1\vee K_5$, $K_4\vee (K_{1, 4}+K_2)$, $K_4\vee (K_1+K_{1, 5})$, $K_3\vee K_{2, 6}$, $K_4\vee (K_1+K_{1, 3}+K_2)$, $K_4\vee (2K_1+K_{1, 4})$, $K_3\vee [(K_2\vee 5K_1)+K_1]$, $K_2\vee 2K_1\vee (K_{1, 4}+K_2)$, $K_4\vee (K_2+K_{1, 2}+2K_1)$, $K_3\vee (K_1+K_{2, 5})$, $K_2\vee K_{3, 6}$, $K_4\vee (K_{1, 3}+3K_1)$, $K_2\vee 2K_1\vee (K_1+K_{1, 3}+K_2)$, $[K_1\vee (K_{1, 4}+K_1)+K_1]\vee K_3$, $K_2\vee 2K_1\vee (2K_1+K_{1, 4})$, $(4K_1+K_2)\vee K_4$, $K_3\vee [K_1+K_1\vee (3K_1+K_2)]$, $6K_1\vee K_4$, $(4K_1+K_2)\vee 2K_1\vee K_2$, $5K_1\vee K_4$, $(K_{1, 3}+K_2)\vee K_3$, $(K_1+K_{1, 4})\vee K_3$, $5K_1\vee 2K_1\vee K_2$, $(K_1+K_{1, 2}+K_2)\vee K_3$, $(2K_1+K_{1, 3})\vee K_3$, $(K_{1, 3}+K_2)\vee 2K_1\vee K_1 \}$.

Proof: Suppose that $G$ is neither a pancyclic graph nor a bipartite graph. According to Lemma 2.1, there is a positive integer $k$ makes $3\leq d_k\leq k < n/2$ and $d_{n-k}\leq n-k-1$ hold at the same time. Then we have

thus

Since

thus $(k-3)(2n-3k-10)\leq 0$. Next, the following two cases are discussed.

Case 1 Assume that $(k-3)(2n-3k-10) = 0$, i.e., $k = 3$ or $2n-3k-10 = 0$. All the above inequalities are equal and $m = \tbinom{n-3}{2}+9$.

Case 1.1 If $k = 3$, then $G$ is a graph with $d_1 = d_2 = d_3 = 3, d_4 = d_5 = \cdots = d_{n-3} = n-4, d_{n-2} = d_{n-1} = d_n = n-1$. Three vertices with degree $n-1$ must be connected to other vertices, then a $K_3$ is obtained. The three vertices with degree $3$ are not connected with other vertices, and a $3K_1$ is obtained. The remaining $n-6$ vertices with degree $n-4$ must be connected to each other to ensure that the degree is $n-4$, so they induce a $K_{n-6}$. According to the above analysis, the graph $G$ is $(3K_1+K_{n-6})\vee K_3$.

Case 1.2 If $2n-3k-10 = 0$, then we get $n\leq 19$ because $\frac{2n-10}{3} = k < \frac{n}{2}$, and hence $n = 11$, $k = 4$, or $n = 14$, $k = 6$, or $n = 17$, $k = 8$. The corresponding permissible graphic sequences are $(4, 4, 4, 4, 6, 6, 6, 10, 10, 10, 10)$, $(6, 6, 6, 6, 6, 6, 7, 7, 13, 13, 13, 13, 13, 13)$, $(8, 8, 8, 8, 8, 8, 8, 8, 8, 16, 16, 16, 16, 16, 16, 16, 16)$. Analysis shows that the graphs $G$ are $(4K_1+K_3)\vee K_4$, $(6K_1+K_2)\vee K_6$ and $9K_1\vee K_8$ respectively.

Case 2 Assume that $(k-3)(2n-3k-10) < 0$, i.e., $k > 3$ and $2n-3k-10 < 0$. Because $2n-10 < 3k < \frac{3}{2}n$, then, $n = 15, k = 7$ or $n = 13, k = 6$ or $n = 12, k = 5$ or $n = 11, k = 5$ or $n = 10, k = 4$ or $n = 9, k = 4$.

Case 2.1 If $n = 15$, $k = 7$. According to equation (3.3), we have $150\leq \Sigma_{i = 1}^{15}d_i\leq 154$. All possible degree sequences and their corresponding graphs are shown in Table 1.

Case 2.2 If $n = 13$, $k = 6$. According to equation (3.3), we have $108\leq \Sigma_{i = 1}^{13}d_i\leq 114$. All possible degree sequences and their corresponding graphs are shown in Table 2.

Case 2.3 If $n = 12$, $k = 5$. According to equation (3.3), we have $90\leq \Sigma_{i = 1}^{12}d_i\leq 92$. All possible degree sequences and their corresponding graphs are shown in Table 3.

Case 2.4 If $n = 11$, $k = 5$. According to equation (3.3), we have $74\leq \Sigma_{i = 1}^{11}d_i\leq 80$. All possible degree sequences and their corresponding graphs are shown in Table 4.

Case 2.5 If $n = 10$, $k = 4$. According to equation (3.3), we have $60\leq \Sigma_{i = 1}^{10}d_i\leq 62$. All possible degree sequences and their corresponding graphs are shown in Table 5.

Case 2.6 If $n = 9$, $k = 4$. According to equation (3.3), we have $48\leq \Sigma_{i = 1}^{9}d_i\leq 52$. All possible degree sequences and their corresponding graphs are shown in Table 6.

Next, we consider the pancyclicity of these graphs. For convenience, we put the maximum length cycle $L(G)$ of $G$ in the appendix. In the following description, when it comes to the description of the graphs, we will use the sequence number of the graphs in the appendix.

As can be seen from the appendix, according to Lemma 2.5, all the graphs of No.5-18 in the appendix are pancyclic. Others belong to $NP_1$ and they are neither pancyclic nor bipartite.

The proof is complete.

Theorem 3.2 Let $G$ be a connected graph with $n(n\geq5)$ vertices and $m$ edges, and its minimum degree $\delta(G)\geq3$. If

then $G$ is a pancyclic graph or a bipartite graph.

Proof: Suppose that $G$ is neither a pancyclic graph nor a bipartite graph. Because a complete graph is a pancyclic graph and $\delta(K_{1, n-1}) = 1$, then $G$ cannot be a complete graph or $K_{1, n-1}$. In such a situation, the equation in Lemma 2.2 is invalid. By Lemma 2.2, $\sqrt{n^2-8n+31}\leq \mu(G) < \sqrt{2m-n+1}$, i.e., $m > \tbinom{n-3}{2}+9$.

By Theorem 3.1, $G$ is a pancyclic graph or a bipartite graph or $G\in NP_1$. It can be calculated that $(3K_1+K_{n-6})\vee K_3$, $(4K_1+K_3)\vee K_4$, $(6K_1+K_2)\vee K_6$, $9K_1\vee K_8$ satisfy $m = \tbinom{n-3}{2}+9$, which is contradiction. Next, we will study whether the graphs of No.19-69 satisfy the spectral radius condition in the Theorem 3.2. Note that $G\in NP_2$ and $NP_2$ is the set of graphs of No.19-69 in the appendix.

Take $(2K_1\vee K_4)\vee7K_1$ as an example:

Let $\textbf{X} = (X_1, X_2, \dots\dots\dots, X_{13})^T$ be the eigenvector corresponding to $\mu(G)$, where $X_i(1\leq i\leq 2)$ corresponds to the vertex of degree 11, $X_i(3\leq i\leq 6)$ corresponds to the vertex of degree 12 and $X_i(7\leq i\leq 13)$ corresponds to the vertex of degree 6. By eigen-equation (2.1), then we have

Transform the above equations into the matrix equation $(A^{'}(G)-\mu (G)I)X^{'} = 0$, where $X^{'} = (X_1, X_3, X_7)^{T}$ and

Let $f(x) = |xI-A^{'}(G)| = x^3-3x^2-50x-70$, then the maximum root of $f(x) = 0$ is $\mu (G) = 9.235$. It can be calculated that $\mu (G) < \sqrt{13^2-8\times13+31}$, which is contradiction. The remaining graphs are studied in the same way, and the results are shown in Table 7.

From Table 7, all graphs in $NP_{2}$ satisfy $\mu(G) < \sqrt{n^2-8n+31}$, a contradiction. The proof is complete.

Theorem 3.3 Let $G$ be a connected graph with $n(n\geq5)$ vertices and minimum degree $\delta(G)\geq3$. If

then $G$ is a pancyclic graph or a bipartite graph or $7K_1\vee K_6$ or $6K_1\vee K_5$ or $5K_1\vee K_4$.

Proof: Suppose that $G$ is neither a pancyclic graph nor a bipartite graph. Because a complete graph is a pancyclic graph and $\delta (K_{1, n-1}) = 1$, then $G$ cannot be a complete graph or $K_{1, n-1}$. In such a situation, the equation in Lemma 2.3 is invalid. By Lemma 2.3, $\frac{24}{n-1}+2n-8\leq q(G) < \frac{2m}{n-1}+n-2$, i.e., $m > \tbinom{n-3}{2}+9$.

By Theorem 3.1, $G$ is a pancyclic graph or a bipartite graph or $G\in NP_1$. It can be calculated that the graphs of $(3K_1+K_{n-6})\vee K_3$, $(4K_1+K_3)\vee K_4$, $(6K_1+K_2)\vee K_6$, $9K_1\vee K_8$ satisfy $m = \tbinom{n-3}{2}+9$, which is contradiction. Next, we will study whether the graphs of No.19-69 satisfy the signless Laplacian spectral radius condition in the Theorem 3.3. Note that $G\in NP_2$.

Take $(2K_1\vee K_4)\vee 7K_1$ as an example:

Let $\textbf{X} = (X_1, X_2, \dots\dots\dots, X_{13})^T$ be the eigenvector corresponding to $\mu(G)$, where $X_i(1\leq i\leq 2)$ corresponds to the vertex of degree 11, $X_i(3\leq i\leq 6)$ corresponds to the vertex of degree 12 and $X_i(7\leq i\leq 13)$ corresponds to the vertex of degree 6. By eigen-equation (2.2), then we have

Transform the above equations into the matrix equation $(Q^{'}(G)-q(G)I)X^{'} = 0$, where $X^{'} = (X_1, X_3, X_7)^{T}$ and

Let $f(x) = |xI-Q^{'}(G)| = x^3-32x^2+271x-536$, then the maximum root of $g(x) = 0$ is $q(G) = 19.528$. It can be calculated that $q(G) < \frac{24}{13-1}+2\times 13-8$, which is contradiction. The remaining graphs are studied in the same way, and the results are shown in Table 7.

From $Table\; 7$, all graphs in $NP_2$ except $G = 7K_1\vee K_6$ and $G = 6K_1\vee K_5$ and $G = 5K_1\vee K_4$ satisfy $q(G) < \frac{24}{n-1}+2n-8$, a contradiction.

The proof is complete.

Acknowledgments

This work is supported by the Natural Science Foundation of China(11871077), the NSF of Anhui Province(1808085MA04), the NSF of Department of Education of Anhui Province(KJ2017A362), and the NSF of Anhui Province(KJ2018A0964), the Deanship of Scientific Research (DSR) at King Abdulaziz University under grant no (RG-19-135-38), the 2019 Teaching and research project of Hefei Preschool Education College (hyzzd2019003).

Conflict of interest

The author declare that he has no competing interest.

Appendix