MathDB
2-dominating sets

Source: Iran pre-preparation course examination 2011- P6

February 25, 2011
probabilitylogarithmscombinatorics proposedcombinatorics

Problem Statement

We call a subset SS of vertices of graph GG, 22-dominating, if and only if for every vertex v∉S,v∈Gv\notin S,v\in G, vv has at least two neighbors in SS. prove that every rr-regular (r≥3)(r\ge3) graph has a 22-dominating set with size at most n(1+ln⁡(r))r\frac{n(1+\ln(r))}{r}.(15 points) time of this exam was 3 hours
Back to ProblemsView on AoPS