Tuyển tập các báo cáo nghiên cứu khoa học ngành toán học tạp chí Department of Mathematic dành cho các bạn yêu thích môn toán học đề tài: Regular factors of regular graphs from eigenvalues. | Regular factors of regular graphs from eigenvalues Hongliang Lu Department of Mathematics Xi an Jiaotong University Xi an Shanxi 710049 P. R. China luhongliang215@ Submitted Apr 5 2010 Accepted Nov 9 2010 Published Nov 26 2010 Mathematics Subject Classifications 05C50 05C70 Abstract Let r and m be two integers such that r m. Let H be a graph with order H size e and maximum degree r such that 2e H r m. We find a best lower bound on spectral radius of graph H in terms of m and r. Let G be a connected r-regular graph of order G and k r be an integer. Using the previous results we find some best upper bounds in terms of r and k on the third largest eigenvalue that is sufficient to guarantee that G has a k-factor when k G is even. Moreover we find a best bound on the second largest eigenvalue that is sufficient to guarantee that G is k-critical when k G is odd. Our results extend the work of Cioaba Gregory and Haemers J. Combin. Theory Ser. B 1999 who obtained such results for 1-factors. 1 Introduction Throughout this paper G denotes a simple graph of order n the number of vertices and size e the number of edges . For two subsets S T c V G let eG S T denote the number of edges of G joining S to T. The eigenvalues of G are the eigenvalues Xi of its adjacency matrix A indexed so that Al X2 Xn. The largest eigenvalue is often called spectral radius. If G is k-regular then it is easy to see that X1 k and also X2 k if and only if G is connected. A matching of a graph G is a set of mutually disjoint edges. A matching is perfect if every vertex of G is incident with an edge of the matching. Let a be a nonnegative integer and we denote a matching of size a by Ma. Let G denote the complement of a graph G. The join G H denotes the graph with vertex V G u V H and edge set E G H E G u E H u xy x G V G and y G V H . This work is supported by the Fundamental Research Funds for the Central Universities. THE ELECTRONIC JOURNAL OF COMBINATORICS 17 2010 R159 1 For a general graph
