- Tytuł:
- Deficiency and Forbidden Subgraphs of Connected, Locally-Connected Graphs
- Autorzy:
-
Li, Xihe
Wang, Ligong - Powiązania:
- https://bibliotekanauki.pl/articles/32083830.pdf
- Data publikacji:
- 2020-02-01
- Wydawca:
- Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
- Tematy:
-
05C40
05C70 - Opis:
- 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.
- Źródło:
-
Discussiones Mathematicae Graph Theory; 2020, 40, 1; 195-208
2083-5892 - Pojawia się w:
- Discussiones Mathematicae Graph Theory
- Dostawca treści:
- Biblioteka Nauki
Artykuł