Deficiency and forbidden subgraphs of connected, locally-connected graphs

A graph G is locally-connected if the neighbourhood N_G(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 β₀=1/2(3+√8k+17)-1, we show that K_1,2, K_1,3, ⋯ , K₁,β₀, K₃ or K₂ V 2K₁ is the required forbidden subgraph. Furthermore, we obtain some similar results about 3-connected, locally-connected graphs. Key Words: deficiency, locally-connected graph, matching, forbidden subgraph.