Abstract:

A {–1, 1}-vertex-labeled d-regular graph with loops having n vertices and h labels 1 is favorable if a majority of its vertices have a positive sum of labels in their neighborhood. Given n and d, what is the minimum h for which there exists a favorable graph? What is the minimum h for which all labeled graphs are favorable? We answer these questions for all odd n and d, interpret the results from a decision point of view, and discuss links to existing literature.