华东师范大学学报(自然科学版) ›› 2003, Vol. 2003 ›› Issue (4): 1-4.

• 论文 •    下一篇

图的代数连通度及其点连通度

肖恩利;束金龙;闻人凯   

  1. 华东师范大学 数学系,上海 200062
  • 收稿日期:1900-01-01 修回日期:1900-01-01 出版日期:2003-12-25 发布日期:2003-12-25

The Algebraic and Vertex Connectivity of Graphs

XIAO en-li; SHU jin-long;WEN ren-kai   

  1. Department of Mathematics,East China Normal University,Shanghai 200062,China
  • Received:1900-01-01 Revised:1900-01-01 Online:2003-12-25 Published:2003-12-25

摘要： G是一个简单图.a(G),k(G)分别为G的代数连通度和点连通度,该文刻画了满足a(G)=k(G)的图.G=(V,E)是一个n阶简单图,点连通度为k(G)≤[n/2].H是G的任意最小点割集,则a(G)=k(G)当且仅当对任意u∈H和v∈V\H,有uv∈E.

关键词: Laplace矩阵, 代数连通度, 点连通度, 线图, Laplace矩阵, 代数连通度, 点连通度, 线图

Abstract:

G is a simple graph with a(G) and k(G), its algebraic and vertex connectivity.This paper finds all the graphs satisfying a(G)=k(G).G=(V,E) is a simple graph of order n with vertex connectivity k(G)≤[n/2],and H is one of G's minimal vertex cut set,then a(G)=k(G) holds if and only if for every u∈H and every v∈V\H, uv∈E.

Key words: algebraic connectivity, vertex connectivity, line graph, Laplace matrix, algebraic connectivity, vertex connectivity, line graph

中图分类号: