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

1. The connectivity of strongly regular graphs Theorem 1.1. (Brouwer& Mesner 4]) Let? be strongly regular of va-

lency k. Then (?)= k, and the only cut sets of size k are the point neighbourhoods.

The weaker result that for strongly regular graphs the edge-connectivity is at least the valency, was shown ten years earlier by Plesnik 10]. Open problems are for example: (3) Prove the above result for distance-regular graphs. (4) Let? be strongly regular with parameters (v; k;; ), and let S be a disconnecting set not containing any point neighbourhood?(x). Show that jS j 2k? 2? . (5) Let S be a disconnecting set such that jS\?(x)j k for some xed, 0<< 1, and all vertices x of?. Prove a superlinear (in k) lower bound for jS j. Godsil 7] conjectures that for any graph that is a colour class in an association scheme, the edge-connectivity equals the degree, and I conjecture the same for the vertex-connectivity. Partial results: Fiedler 6] shows that the vertex-connectivity of a graph is at least k? 2, where k is the degree and 2 the second largest eigenvalue. Lovasz 9], Problem 12.14, proves that the edge-connectivity of a vertextransit

ive graph is at least its degree. An old result says that the vertexconnectivity of a vertex-transitive graph is at least 2(k+ 1)=3, where the extreme case is the clique extension of a circuit. Brouwer& Mulder 5] showed (?)= k for graphs with the property that any two distinct vertices have either 0 or 2 common neighbours. This settles (3) in the case 2 f0; 2g,= 2. 2. The connectedness of generic pieces of generalized polygons Theorem 2.1. (Brouwer 2]) Let? be the point graph or the ag graph of

a nite generalized polygon. Then the subgraph of? induced on the set of all vertices far away from (`in general position w.r.t.') a point or ag is connected, except in the cases G2 (2), 2 F4 (2) and (for the ag graph) B2 (2), G2 (3). A similar result holds more generally for the complement of a geometric hyperplane.

Open problems: (6) Generalize this to near polygons. (7) Generalize this to distance-regular graphs. It is very easy to see that in a strongly regular graph the subgraph on the vertices far away from a point is connected (except when the graph is complete multipartite). 38

上一页第2页

你可能喜欢

热门文档

相关文档

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