- Tytuł:
- On Selkow’s Bound on the Independence Number of Graphs
- Autorzy:
-
Harant, Jochen
Mohr, Samuel - Powiązania:
- https://bibliotekanauki.pl/articles/31343349.pdf
- Data publikacji:
- 2019-08-01
- Wydawca:
- Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
- Tematy:
-
graph
independence number - Opis:
- For a graph $G$ with vertex set $ V (G) $ and independence number $ \alpha (G) $, Selkow [A Probabilistic lower bound on the independence number of graphs, Discrete Math. 132 (1994) 363–365] established the famous lower bound \( \sum_{ v \in V (G) } \tfrac{1}{d(v)+1} ( 1+ \max \{ \tfrac{ d(v) }{ d(v)+1 } - \sum_{ u \in N(v) } \tfrac{1}{ d(u)+1 },0 \} ) \) on $ \alpha (G) $, where $ N(v) $ and $ d(v) = | N(v) | $ denote the neighborhood and the degree of a vertex $ v \in V (G) $, respectively. However, Selkow’s original proof of this result is incorrect. We give a new probabilistic proof of Selkow’s bound here.
- Źródło:
-
Discussiones Mathematicae Graph Theory; 2019, 39, 3; 655-657
2083-5892 - Pojawia się w:
- Discussiones Mathematicae Graph Theory
- Dostawca treści:
- Biblioteka Nauki
Artykuł