关于临界h棱连通图的最大棱数及最大图的结构(Ⅱ)——临界h棱连通图的性质和最大临界3棱连通图类的刻划

ON THE SIZE AND THE STRUCTURES OF MAXIMUM CRITICALLY H-EDGE-CONNECTED GRAPHS (Ⅱ)—Some Properties and the Characterization of Maximum Critically 3-Edge-Connected Graphs

设λ(G)表示G的棱连通度,图G称为临界h棱连通的,如果λ(G)=h而且对任何x∈V(G),λ(G-x)≤h-1,具有最大棱数的临界h棱连通图称为最大临界h棱连通图.本文首先证明对h≥3的临界h棱连通图的若干性质,然后证明最大临界3棱连通图的每个顶点都与3度点相邻,并由此给出了此类图的结构刻划和最大棱数.

A graph G is called to be criticalty h-egde-connected if it is h-egde-connected and deleting any arbitrarily chosen vertex from G always leaves a graph which is not h-egde-connected A critically h-egde-connected graph G is called to be maximum if it has th greatest size among all such graphs of the same order as G.Some properties of critically h-egde connected graphs are given and the struc-ture of maximum critically 3-egde-connected graphs are fully characterized in this paper.