tailieunhanh - Báo cáo toán học: "On the First Eigenvalue of Bipartite 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: On the First Eigenvalue of Bipartite Graphs. | On the First Eigenvalue of Bipartite Graphs Amitava Bhattacharya School of Mathematics Tata Institute of Fundamental Research Homi Bhabha Road Colaba Mumbai 400005 INDIA amitava@. in Shmuel Friedland Department of Mathematics Statistics and Computer Science University of Illinois at Chicago Chicago Illinois 60607-7045 USA friedlan@ Uri N. Peled Department of Mathematics Statistics and Computer Science University of Illinois at Chicago Chicago Illinois 60607-7045 USA uripeled@ Submitted Sep 19 2008 Accepted Nov 18 2008 Published Nov 30 2008 Mathematics Subject Classification 05C07 05C35 05C50 15A18 Abstract In this paper we study the maximum value of the largest eigenvalue for simple bipartite graphs where the number of edges is given and the number of vertices on each side of the bipartition is given. We state a conjectured solution which is an analog of the Brualdi-Hoffman conjecture for general graphs and prove the conjecture in some special cases. Key words. Bipartite graph maximal eigenvalue Brualdi-Hoffman conjecture degree sequences chain graphs. 1 Introduction The purpose of this paper is to study the maximum value of the maximum eigenvalue of certain classes of bipartite graphs. These problems are analogous to the problems Visiting Professor Fall 2007 - Winter 2008 Berlin Mathematical School Berlin Germany THE ELECTRONIC JOURNAL OF COMBINATORICS 15 2008 R144 1 considered in the literature for general graphs and 0 1 matrices 1 2 3 5 8 . We describe briefly the main problems and results obtained in this paper. We consider only finite simple undirected graphs bipartite graphs G. Let G V u W E where V v1 . vm W w1 . wn are the two set of vertices of G. We view the undirected edges E of G as a subset of V X W. Denote by deg V deg Wj the degrees of the vertices vi Wj respectively. Let D G d1 G d2 G dm G be the rearranged set of the degrees deg V1 . deg vm. Note that e G 2m1 deg vi is the number of edges in G. Denote by Amax G the .