The Minimum Size of Critically m-Neighbour-Connected Graphs

Abstract

A graph $G$ is said to be $m$-neighbour-connected if the neighbour-connectivity of the graph, $K(G)=m$. A graph $G$ is said to be critically $m$-neighbour-connected if it is $m$-neighbour-connected and the removal of the closed neighbourhood of any one vertex yields an $(m-1)$-neighbour-connected subgraph. In this paper, we give some upper bounds of the minimum size of the critically $m$-neighbour-connected graphs of any fixed order $v$, and show that the number of edges in a minimum critically $m$-neighbour-connected graph with order $v$ (a multiple of $m$) is $\lceil \frac{1}{2}mv\rceil$.