- Tytuł:
- Making a Dominating Set of a Graph Connected
- Autorzy:
-
Li, Hengzhe
Wu, Baoyindureng
Yang, Weihua - Powiązania:
- https://bibliotekanauki.pl/articles/31342251.pdf
- Data publikacji:
- 2018-11-01
- Wydawca:
- Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
- Tematy:
-
independent set
dominating set
connected dominating set - Opis:
- Let $ G = (V,E) $ be a graph and $ S \subseteq V $. We say that $ S $ is a dominating set of $ G $, if each vertex in $ V \backlash S $ has a neighbor in $S$. Moreover, we say that $S$ is a connected (respectively, 2-edge connected or 2-connected) dominating set of $G$ if $ G[S] $ is connected (respectively, 2-edge connected or 2-connected). The domination (respectively, connected domination, or 2-edge connected domination, or 2-connected domination) number of $G$ is the cardinality of a minimum dominating (respectively, connected dominating, or 2-edge connected dominating, or 2-connected dominating) set of $G$, and is denoted $ \gamma (G) $ (respectively $ \gamma_1 (G) $, or $ \gamma_2^′ (G) $, or $ \gamma_2 (G) $). A well-known result of Duchet and Meyniel states that $ \gamma_1 (G) \le 3 \gamma (G) − 2 $ for any connected graph $G$. We show that if $ \gamma (G) \ge 2 $, then $ \gamma_2^′ (G) \ge 5 \gamma (G) − 4 $ when $G$ is a 2-edge connected graph and $ \gamma_2 (G) \le 11 \gamma (G) − 13 $ when $G$ is a 2-connected triangle-free graph.
- Źródło:
-
Discussiones Mathematicae Graph Theory; 2018, 38, 4; 947-962
2083-5892 - Pojawia się w:
- Discussiones Mathematicae Graph Theory
- Dostawca treści:
- Biblioteka Nauki
Artykuł