Spectral radius and traceability of graphs with large minimum degree

ABSTRACT

Let $\mu \left(G\right)$ and $\delta \left(G\right)$ be the spectral radius and the minimum degree of a graph G, respectively. In this paper, we obtain spectral conditions for a graph to be traceable among graphs (balanced bipartite graphs) with large minimum degree. The main results are listed as:

1. Let G be a graph with order $n\ge max\{\frac{1}{2}{k}^3+\frac{1}{2}{k}^2+k+5,6k+10\}$ and $\delta \left(G\right)\ge k$, where $k\ge 1$ is an integer. If $\mu \left(G\right)\ge n-k-2,$ then G is traceable unless $G=L_n^k$ or $N_n^k$.

2. Let G be a balanced bipartite graph with order $2n$ and $\delta \left(G\right)\ge k$, where $k\ge 2$ and $n\ge \frac{1}{2}{k}^3+\frac{1}{2}{k}^2+2k+7$. If $\mu \left(G\right)\ge \sqrt{n(n-k-1)},$ then G is traceable unless $G=Q_n^k$, where $Q_n^k$ is the graph obtained from $K_{n,n}$ by deleting $E\left(K_{n-k,k+1}\right)$.

KEYWORDS:

• Spectral radius
• traceable
• minimum degree

AMS SUBJECT CLASSIFICATIONS:

• 05C50
• 15A18

Acknowledgements

The authors are grateful to the anonymous referees for their valuable comments, suggestions and corrections which improved the presentation of this paper.

Disclosure statement

No potential conflict of interest was reported by the authors.

Additional information

Funding

This work was supported by Natural Science Foundation of Guangdong Province [grant number 2014A030313640].