多重图的线图连通度  

Connectivities of Line Graphs Over Multigraphs

作　　者：田玉芳[1] 何中市[2] 

机构地区：[1]重庆大学数理学院,重庆400030 [2]重庆大学计算机学院,重庆400030

出　　处：《重庆大学学报（自然科学版）》2005年第10期94-98,共5页Journal of Chongqing University

基　　金：国家自然科学基金资助项目(60173060)

摘　　要：提出了多重图的线图的概念,研究了多重图的线图连通度的上界和下界.刻画了图的最小度与其线图连通度的关系:若δ(G)≥μ(﹂p/2」+1),则κL(G)≥Lδ(G)-2(μ-1),并通过构造出一系列的图,证明此结果是最好的:条件不能够被削弱,结论不能够被加强.同时,揭示了图的限制性边连通度就是线图连通度,推广了已有文献的结果.The previous concept of line graph is generalized, and the concept of line graph over multigraph is proposed. The line graph of a multigraph G,L（ G）, is defined to be a graph whose vertices are the edges in G, and there are exactly m edges between two vertices of L（G） if and only if they have exactly m common vertices in G. Both lower bounds and upper bounds are obtained. Furthermore, a sharp lower bound of the connectivities of L（G） is given as follows. For a p-vertex μ-multiple multigraph G, let κL （G） and δL （G） denote the connectivity and the minimum degree of L （G）, respectively. If the minimum degree δ（C）≥μ（[p/2]＋1）, then κL（C）≥δL（C）-2（μ-1）. It is shown that the lower bound is best possible. It improves the results on the subject.

关 键 词：连通度 限制性边连通度 线图 多重图 

分 类 号：O157.5[理学—数学]