Let G be a graph with 3n vertices, with the property that every pair of vertices has codegree at least 1. That is, ∀x∀y∃z such that xz and yz are both edges. Show that G has a dominating set of size n. 

I do not understand the following proof;i dont understand the part "this is at most $e^{−np2}≤ e^{− log n} = n^{−1}$. Therefore, a union bound over the n choices of v produces the result." and also the neighbor part; if anyone could explain what the last paragraph of the proof means that would be great thanks.


The codegree condition implies that the diameter of the graph is at most 2. We prove that every $n$-vertex graph with diameter $\leq 2$ has a dominating set (a subset $S$ of vertices such that every other vertex is either in, or has a neighbor in $S$) of size only $\leq\sqrt{nlogn}+1$

To see this, let $p =\sqrt{log n/n}$

Observe that since the diameter is at most 2, if any vertex has degree ≤ np, then its neighborhood already is a dominating set of suitable size. Therefore, we may assume that all vertices have degree strictly greater than np. It feels “easy” to find a small dominating set in this graph because all degrees are high. Consider a random sample of np vertices (selected uniformly at random, with replacement), and let S be their union. Note that $|S| \leq np$. Now the probability that a particular fixed vertex $v$ fails to have a neighbor in S is strictly less than $(1 −p)^np$, because we need each of np independent samples to miss the neighborhood of v. This is at most $e^{−np2}≤ e^{− log n} = n^{−1}$. Therefore, a union bound over the $n$ choices of $v$ produces the result.

  • $\begingroup$ What is that from? If you are quoting someone else's words, you must give them due credit. $\endgroup$ – bof May 12 '19 at 4:49
  • $\begingroup$ Also, if one of us happens to have access to a copy of that textbook, that may make it easier to answer your question. $\endgroup$ – bof May 12 '19 at 4:50
  • $\begingroup$ its from an online pdf textbook of random graph theory questions $\endgroup$ – james black May 12 '19 at 5:00
  • $\begingroup$ sorry not exactly a book $\endgroup$ – james black May 12 '19 at 5:00
  • $\begingroup$ Well how about a link? And it still must have an author. Is it anonymous? $\endgroup$ – bof May 12 '19 at 5:10

Some of what you have written isn't right in terms of what appears in the exponents; perhaps this is a formatting error rather than errors in the source material.

The neighbourhood of $v$ has more than $np$ vertices, so less than $n-np$ out of $n$ vertices are not neighbours of $v$. Thus the probability that a random vertex is not in the neighbourhood is $< (1-p)$, and the probability that none of the $np$ random vertices are is $<(1-p)^{np}$.

Now $(1-p)\leq e^{-p}$ from looking at the graphs, so $(1-p)^{np}\leq e^{-n^2p}=e^{-\log n}=\frac1n$.

Since the probability that a particular vertex $v$ is not covered is $<1/n$, the chance that some vertex is not covered is $<\frac1n\times n$ by adding up all the individual probabilities. Since the probability is less than $1$, it is possible that this doesn't happen, i.e. you chose a dominating set. So a dominating set must exist.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.