| Autor: |
Kir��ly, Zolt��n, Kulkarni, Neeraja, McMeeking, Ian, Mundinger, Joshua |
| Rok vydání: |
2018 |
| Předmět: |
|
| DOI: |
10.48550/arxiv.1808.05835 |
| Popis: |
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. |
| Databáze: |
OpenAIRE |
| Externí odkaz: |
|
