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 $ \text{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 $ \text{def} (G) \le 1 $. In this paper, we extend this result to the condition of $ \text{def} (G) \le k $, where k is a positive integer. Let $ \beta_0 = \ceil{ 1/2 (3+\sqrt{8k+17} ) } −1 $, we show that $ K_{1,2}, K_{1,3}, . . ., K_{1,β_0}, K_3 $ or \( K_2 \lor 2K_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.
Ta witryna wykorzystuje pliki cookies do przechowywania informacji na Twoim komputerze. Pliki cookies stosujemy w celu świadczenia usług na najwyższym poziomie, w tym w sposób dostosowany do indywidualnych potrzeb. Korzystanie z witryny bez zmiany ustawień dotyczących cookies oznacza, że będą one zamieszczane w Twoim komputerze. W każdym momencie możesz dokonać zmiany ustawień dotyczących cookies
Informacja
SZANOWNI CZYTELNICY!
UPRZEJMIE INFORMUJEMY, ŻE BIBLIOTEKA FUNKCJONUJE W NASTĘPUJĄCYCH GODZINACH:
Wypożyczalnia i Czytelnia Główna: poniedziałek – piątek od 9.00 do 19.00