Journal article
Some Sharp Bounds on the Negative Decision Number of Graphs
Discussiones Mathematicae. Graph Theory, v 33(4), pp 649-656
01 Sep 2013
Featured in Collection : UN Sustainable Development Goals @ Drexel
Abstract
Let G = (V,E) be a graph. A function f : V → {-1,1} is called a bad function of G if ∑
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 ∑
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.
Metrics
5 Record Views
Details
- Title
- Some Sharp Bounds on the Negative Decision Number of Graphs
- Creators
- Hongyu Liang - Tsinghua University
- Publication Details
- Discussiones Mathematicae. Graph Theory, v 33(4), pp 649-656
- Publisher
- Versita
- Resource Type
- Journal article
- Language
- English
- Academic Unit
- School of Biomedical Engineering, Science, and Health Systems
- Web of Science ID
- WOS:000345240700002
- Scopus ID
- 2-s2.0-84885361052
- Other Identifier
- 991019320609004721
UN Sustainable Development Goals (SDGs)
This publication has contributed to the advancement of the following goals:
InCites Highlights
Data related to this publication, from InCites Benchmarking & Analytics tool:
- Web of Science research areas
- Mathematics