On Criticality of Critically h-edge-connected Graphs
LI Yong-jie · Mathematica Applicata · 2008
A graph G is said to be k-critically h-edge-connected if λ(G)=h and for every set of k vertices {u1,…,uk},λ(G-{u1,…,ui})≤λ(G-{u1,…,ui-1})-1,i≤k.If G is k-critically h-edge-connected but not(k+1)-critically hedge-connected,then we denote it by(h*,k*)λ-graph.It is proved that there exists an(h*,k*)λ-graph G,iff(i)1≤k≤[(h+1)/2],h≡0,1,2(mod 4)and 1≤k≤[(h-1)/2],h≡3(mod 4) or(ii)k=h and G=Kh+1.