Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: negative decision number

Sortuj według:

Ogranicz wyniki do:

Some Sharp Bounds on the Negative Decision Number of Graphs

100%

Liang H.

Discussiones Mathematicae Graph Theory

2013

tom 33

nr 4

649-656

Let G = (V,E) be a graph. A function f : V → {-1,1} is called a bad function of G if ∑u∈NG(v) f(u) ≤ 1 for all v ∈ V where NG(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.

Ograniczanie wyników

1 Discussiones Mathematicae Graph Theory

1 Liang H.

1 2013

Wyniki wyszukiwania

Some Sharp Bounds on the Negative Decision Number of Graphs