The Minimum Size of Critically m-Neighbour-Connected Graphs

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 \(\left\lceil\frac{1}{2}mv\right\rceil\).