Neighbor‐connected graphs and projective planes
G. Günther, Bert L. Hartnell, Richard J. Nowakowski · Networks · 1987
Abstract 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)| ≧ k2 + (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.