文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > 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

regular of valency k, and with eigenvalues k= 1:= 2maxv j j j: j Then

3. The toughness of a regular graph Theorem 3.1. (Alon-Brouwer, cf. 1, 3]) Let? be a graph on v vertices, 2

:::

v.

Put

t(?)> k? 2:

Open problems: (8) Prove t(?) k? 1. (I conjecture that this is the right bound.) (9) Prove t(?)= k in many cases. Examples We have bipartite graphs of small toughness, so the`?1' would be best possible. The Delsarte-Ho man bound for cocliques C in strongly regular graphs states If equality holds, and=? v (as is often the case), then we nd with S=?nC: t(?) (v? jC j)=jC j= k . How are these results proved? Essentially, only interlacing (cf. Haemers 8]) is used. Interlacing comes in two main forms: (i) If is an induced subgraph of a graph?, then the eigenvalues j (1 j u) of interlace the eigenvalues i (1 i v) of?: we have i i (1 i u) and u?j v?j (0 j u? 1). (ii) Given a partition of the index set of a symmetric matrix A, let B= (BR;S )R;S2 be the matrix of average row sums of the corresponding submatrices of A. Then the eigenvalues of B interlace those of A. Examples Lemma 4.1. The average valency of a graph is not more than its largest eigen4. Tools

v jC j 1+ k=(? ): v

value.

Proof. Use a partition with 1 part.

2

Lemma 4.2. Let? be regular of valency k on v vertices, and let the graph induced on the r-set R have average valency kR . Then 2 (vkR? rk )=(v? r) v; (and hence r v(kR? v )=(k? v ): For kR= 0 we nd the Delsarte-Ho man bound).

39

上一页第3页

你可能喜欢

热门文档

相关文档

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