Autor: Mohr, Samuel - Prolib Integro

Skocz do pozycji: 1.

Tytuł:: New bounds on domination and independence in graphs
Autorzy:: Harant, Jochen
Mohr, Samuel
Tematy:: undirected graph
domination number
independence number
bounds; Pokaż więcej
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Powiązania:: https://bibliotekanauki.pl/articles/59898544.pdf Link otwiera się w nowym oknie
Opis:: We propose new bounds on the domination number and on the independence number of a graph and show that our bounds compare favorably to recent ones. Our bounds are obtained by using the Bhatia-Davis inequality linking the variance, the expected value, the minimum, and the maximum of a random variable with bounded distribution.
Dostawca treści:: Biblioteka Nauki

Artykuł

Skocz do pozycji: 2.

Tytuł:: On Selkow’s Bound on the Independence Number of Graphs
Autorzy:: Harant, Jochen
Mohr, Samuel
Tematy:: graph
independence number; Pokaż więcej
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Powiązania:: https://bibliotekanauki.pl/articles/31343349.pdf Link otwiera się w nowym oknie
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.
Dostawca treści:: Biblioteka Nauki

Artykuł

Skocz do pozycji: 3.

Artykuł

Skocz do pozycji: 4.

Tytuł:: Longer Cycles in Essentially 4-Connected Planar Graphs
Autorzy:: Fabrici, Igor
Harant, Jochen
Mohr, Samuel
Schmidt, Jens M.
Tematy:: essentially 4-connected planar graph
longest cycle
circumference
shortness coefficient; Pokaż więcej
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Powiązania:: https://bibliotekanauki.pl/articles/32083770.pdf Link otwiera się w nowym oknie
Opis:: A planar 3-connected graph $G$ is called essentially 4-connected if, for every 3-separator $S$, at least one of the two components of $G − S$ is an isolated vertex. Jackson and Wormald proved that the length $ \text{circ} (G) $ of a longest cycle of any essentially 4-connected planar graph $G$ on n vertices is at least $ \frac{ 2n+4 }{5} $ and Fabrici, Harant and Jendrol’ improved this result to $ \text{circ} (G) \ge 1/2 (n+4) $. In the present paper, we prove that an essentially 4-connected planar graph on $n$ vertices contains a cycle of length at least $ 3/5 (n+2) $ and that such a cycle can be found in time $ O(n^2) $.
Dostawca treści:: Biblioteka Nauki

Artykuł

Informacja