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 β 0 = ? 1 2 ( 3 + 8 k + 17 ) ? ? 1 , we show that K _(1,2), K _(1,3), . . . , K _(1, β _(0)), K _(3) or K _(2) ∨ 2 K _(1) 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.