Neighbor‐connected graphs and projective planes

In [G. Gunther, Neighbor‐connectivity in regular graphs. Discrete Appl. Math. 11 (1985) 233–243] Gunther introduced the concept of a k neighbor‐connected graph, which has the property that the removal of any k − 1 closed neighborhoods neither disconnects the graph, nor leaves only a complete graph. In this paper we pursue the investigation of minimal graphs that are k ‐regular in addition to being k neighbor‐connected. In a private communication, Gunther conjectured that if G is such a graph which contains no cliques of size larger than m , then |V( G )| ≧ k 2 + ( k + 1 − m ) ( k − 1) + 1. In the above reference, he proved that this conjecture is valid in the case that m = k and characterized the minimal graphs. In this paper, we begin to investigate the case where m = 2. We give some results connecting the minimal graphs to other combinatorial objects.