Constructs new families of regular graphs with the MMS property, identifies high-probability regimes in Erdős–Rényi graphs, and extends sufficient conditions to hypergraphs using pseudo-matchings and blowout constructions.
The Manickam-Mikl\'os-Singhi Parameter of Graphs and Degree Sequences
1 Pith paper cite this work. Polarity classification is still indexing.
1
Pith paper citing it
abstract
Let $G$ be a simple graph. Consider all weightings of the vertices of $G$ with real numbers whose total sum is nonnegative. How many edges of $G$ have endpoints with a nonnegative sum? We consider the minimum number of such edges over all such weightings as a graph parameter. Computing this parameter has been shown to be NP-hard but we give a polynomial algorithm to compute the minimum of this parameter over realizations of a given degree sequence. We also completely determine the minimum and maximum value of this parameter for regular graphs.
fields
math.CO 1years
2026 1verdicts
UNVERDICTED 1representative citing papers
citing papers explorer
-
The Manickam-Mikl\'os-Singhi Property in Graphs and Hypergraphs
Constructs new families of regular graphs with the MMS property, identifies high-probability regimes in Erdős–Rényi graphs, and extends sufficient conditions to hypergraphs using pseudo-matchings and blowout constructions.