tailieunhanh - Báo cáo toán học: "he spectral radius of subgraphs of regular graphs"

Tuyển tập các báo cáo nghiên cứu khoa học về toán học trên tạp chí toán học quốc tế đề tài: The spectral radius of subgraphs of regular graphs. | The spectral radius of subgraphs of regular graphs Vladimir Nikiforov Department of Mathematical Sciences University of Memphis Memphis TN 38152 USA Submitted May 25 2007 Accepted Sep 30 2007 Published Oct 5 2007 Mathematics Subject Classification 05C50 Abstract Let ụ G and ụmin G be the largest and smallest eigenvalues of the adjacency matrix of a graph G. Our main results are i Let G be a regular graph of order n and finite diameter D. If H is a proper subgraph of G then ụ G - ụ H nD. ii If G is a regular nonbipartite graph of order n and finite diameter D then ụ G ụmin G nD Keywords smallest eigenvalue largest eigenvalue diameter connected graph nonbipartite graph Main results Our notation follows 1 . Specifically ụ G and ụmin G stand for the largest and smallest eigenvalues of the adjacency matrix of a graph G. The aim of this note is to improve some recent results on eigenvalues of subgraphs of regular graphs. Cioaba 2 Corollary showed that if G is a regular graph of order n and e is an edge of G such that G e is a connected graph of diameter D then ụ G _ ụ G _ e 5. nD The approach of 3 helps improve this assertion in a natural way Theorem 1 Let G be a regular graph of order n and finite diameter D. If H is a proper subgraph of G then ụ G - ụ H -L 1 THE ELECTRONIC JOURNAL OF COMBINATORICS 14 2007 N20 1 Since p H p H0 whenever H c H0 we may assume that H is a maximal proper subgraph of G that is to say V H V G and H differs from G in a single edge. Thus we can deduce Theorem 1 from the following assertion. Theorem 2 Let G be a regular graph of order n and finite diameter D. If uv is an edge of G then . Í 1 nD if G uv is connected uv ị 1 n _ 3 D 1 otherwise. Furthermore Theorem 1 implies a result about nonbipartite graphs. Theorem 3 If G is a regular nonbipartite graph of order n and finite diameter D then p G pmin G -py nD Finally we note the following more general version of the lower bound in Corollary in 2 . Lemma 4 Let G be a connected regular graph