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
Spectrum and connectivit... 暂无评价 4页 免费 CONNECTIVITY AND PLAN... ... Conjectures on index and algebraic connectivity of graphs 化学指数化学指数...
Connectivity of Planar G... 暂无评价 13页 免费 Spectrum and connectivit....The minimal connected generalized knight's graphs are shown to be planar or...
Spectrum and connectivit... 暂无评价 4页 免费 Connectivity and Transpo......93–105 (2001) Connectivity of Planar Graphs H. de Fraysseix P. Ossona ...
Connectivity of Planar G... 暂无评价 13页 免费 Spectrum and connectivit....Explicit construction algorithms exist for Ramanujan graphs that create regular ...
Connectivity and Transpo... 暂无评价 8页 2.00元 Spectrum and connectivit...ection positivity, rank connectivity, and homomorphism of graphs ? ? ? ? ...
Spectrum and connectivit... 暂无评价 4页 免费 Connectivity and Transpo......93–105 (2001) Connectivity of Planar Graphs H. de Fraysseix P. Ossona ...
3-restricted connectivity of graphs with given girth_专业资料。维普资讯 http://www.cqvip.com Ap.MahJp1t..Chis neeUni v 20,33:5-5 082()3138 3rs...
[5] G. Chartrand and M. J. Stewart, The connectivity of line graphs, Ann., 182 (1969) 170-174. Math. [6] T. Hamada, T. Nonaka, and I. ...
The m-connectivity index of graphs Hao Li? Mei Lu? ? Department of Mathematical Sciences, Tsinghua University, Beijing 100084, China (Received November ...
Connectivity and Transportation Description of Graphs_专业资料 暂无评价
热门文档