Pavel Chebotarev – Majority domination on regular graphs: A new look

Pavel Chebotarev – Majority domination on regular graphs: A new look

Pavel Chebotarev – Majority domination on regular graphs: A new look

Wednesday, March 29, 2023
  • Lecturer: Pavel Chebotarev
  • Location: 814 Amado
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.

Print to PDF