We call a subset S of vertices of graph G, 2-dominating, if and only if for every vertex v∈/S,v∈G, v has at least two neighbors in S. prove that every r-regular (r≥3) graph has a 2-dominating set with size at most rn(1+ln(r)).(15 points)
time of this exam was 3 hours probabilitylogarithmscombinatorics proposedcombinatorics