文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > Spectrum and connectivity of graphs
侵权投诉

Spectrum and connectivity of graphs

Problem. Let \Gamma be a nice graph. Show that \Gamma is very connected. In this talk I would like to give three examples of results about the connectivity of a graph that follow by considering its spectrum. There are lots of open problems. Three measures

Volume 9 (1& 2) 1996, pp. 37{ 40

Spectrum and Connectivity of Graphs Technical University Eindhoven, Department of Mathematics, P.O. Box 513, 5600 MB Eindhoven The Netherlands e-mail aeb@win.tue.nl

A.E. Brouwer

Problem. Let? be a nice graph. Show that? is very connected. In this talk I would like to give three examples of results about the connectivity of a graph that follow by considering its spectrum. There are lots of open problems. Three measures of connectivity play a r^le here: o (i) is? connected or not? (ii) (?), the vertex connectivity of?, that is, the minimum number of vertices that one has to remove in order to disconnect?. (iii) t(?), the toughness of?, is de ned as

where S runs over all sets of vertices such that? n S is disconnected, and c(? n S ) is its number of connected components. The graph K0 without vertices is not connected (we have c(K0 )= 0, while c(?)= 1 for connected graphs?) but I shall leave unde ned whether it is disconnected, and hence do not de ne (?) and t(?) when? is complete. 4 For example, for the Petersen graph we nd (?)= 3 and t(?)= 3 . More generally, we clearly have (?) k(?) if k(?) is the (minimal) valency of?. One may also ask about the size of`nonlocal' cut sets. For example, (1) (`unimodality') Is it true that if S is a cut set of?, with separation? n S= A+ B, then min(j?(S )\ Aj; j?(S )\ B j) jS j? (Here?(S ) denotes the set of all vertices adjacent to some vertex of S .) (Jack Koolen remarks that some condition is necessary: for each i, 0 i 17, the Biggs-Smith graph has a cut set S of size 17 such that j?(S )\ Aj= 17+ i, j?(S )\ B j= 34? i.) (2) Show that jS j is substantially larger than k when S is nonlocal (say, given a lower bound on the size or the minimum valency of each component of? n S ).

j min c(?S j S ) S n

37

Spectrum and connectivity of graphs

第1页

你可能喜欢

热门文档

相关文档

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email