Deficiency and Forbidden Subgraphs of Connected, Locally-Connected Graphs

A graph G is locally-connected if the neighbourhood NG(v) induces a connected subgraph for each vertex v in G. For a graph G, the deficiency of G is the number of vertices unsaturated by a maximum matching, denoted by def(G). In fact, the deficiency of a graph measures how far a maximum matching is from being perfect matching. Saito and Xiong have studied subgraphs, the absence of which forces a connected and locally-connected graph G of sufficiently large order to satisfy def(G) ≤ 1. In this paper, we extend this result to the condition of def(G) ≤ k, where k is a positive integer. Let β0=⌈12(3+8k+17)⌉−1{\beta _0} = \left\lceil {{1 \over 2} ( {3 + \sqrt {8k + 17} } )} \right\rceil - 1 , we show that K1,2, K1,3, . . . , K1,β0, K3 or K2 ∨ 2K1 is the required forbidden subgraph. Furthermore, we obtain some similar results about 3-connected, locally-connected graphs.