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 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 \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 K1,2, K1,3, ..., K1,β0, K3 or K2\vee 2K1 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:
PDF