Authors: X. Li, L. Wang Title: Deficiency and forbidden subgraphs of connected , locally-connected graphs Source: Discussiones Mathematicae Graph Theory Received 08.09.2017, Revised 26.02.2018, Accepted 26.02.2018, doi: 10.7151/dmgt.2121 | |
Abstract: 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 \dif(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 \dif(G)≤ 1. In this paper, we extend this result to the condition of \dif(G)≤ k, where k is a positive integer. Let β_{0}= \left⌈ \frac{1}{2}(3+\sqrt{8k+17})\right⌉ -1, we show that K_{1,2}, K_{1,3}, ..., K_{1,β0}, K_{3} or K_{2}\vee 2K_{1} is the required forbidden subgraph. Furthermore, we obtain some similar results about 3-connected, locally-connected graphs. | |
Keywords: deficiency, locally-connected graph, matching, forbidden subgraph | |
Links: |