TR-2018-11

The Manickam-Miklós-Singhi Parameter of Graphs and Degree Sequences

Zoltán Király, Neeraja Kulkarni, Ian McMeeking, Joshua Mundinger



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.


Bibtex entry:

@techreport{egres-18-11,
AUTHOR = {Kir{\'a}ly, Zolt{\'a}n and Kulkarni, Neeraja and McMeeking, Ian and Mundinger, Joshua},
TITLE = {The Manickam-Miklós-Singhi Parameter of Graphs and Degree Sequences},
NOTE= {{\tt egres.elte.hu}},
INSTITUTION = {Egerv{\'a}ry Research Group, Budapest},
YEAR = {2018},
NUMBER = {TR-2018-11}
}


Last modification: 10.9.2021. Please email your comments to Tamás Király!