- Tytuł:
- Some Sharp Bounds on the Negative Decision Number of Graphs
- Autorzy:
- Liang, Hongyu
- Powiązania:
- https://bibliotekanauki.pl/articles/29785048.pdf
- Data publikacji:
- 2013-09-01
- Wydawca:
- Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
- Tematy:
-
negative decision number
bad function
sharp upper bounds
Nordhaus-Gaddum results - Opis:
- Let $G = (V,E)$ be a graph. A function $f : V → {-1,1}$ is called a bad function of $G$ if $∑_{u∈N_G(v)} f(u) ≤ 1$ for all $v ∈ V$ where $N_G(v)$ denotes the set of neighbors of $v$ in $G$. The negative decision number of $G$, introduced in [12], is the maximum value of $∑_{v∈V} f(v)$ taken over all bad functions of $G$. In this paper, we present sharp upper bounds on the negative decision number of a graph in terms of its order, minimum degree, and maximum degree. We also establish a sharp Nordhaus-Gaddum-type inequality for the negative decision number.
- Źródło:
-
Discussiones Mathematicae Graph Theory; 2013, 33, 4; 649-656
2083-5892 - Pojawia się w:
- Discussiones Mathematicae Graph Theory
- Dostawca treści:
- Biblioteka Nauki
Artykuł