Edge Cover Time for Regular Graphs

Roberto Tauraso Dipartimento di Matematica Università di Roma “Tor Vergata” via della Ricerca Scientifica 00133 Roma Italy

                    tauraso@mat.uniroma2.it

Abstract Consider the following stochastic process on a graph: initially all vertices are uncovered and at each step cover the two vertices of a random edge. What is the expected number of steps required to cover all vertices of the graph? In this note we show that the mean cover time for a regular graph of N vertices is asymptotically (N log N)/2. Moreover, we compute the exact mean cover time for some regular graphs via generating functions.

1 Introduction

The classical coupon collector’s problem can be extended in many ways. In some variants that can be found in the literature (see, for example, [1, 2, 3, 4]) the objects to be collected are the vertices of a graph. There are various interesting collection processes (e.g., a random walk through the graph), but the following one does not seem to have been considered much. Let G be a connected graph with N ≥ 2 vertices and M ≥ 1 edges (no loops). An edge covering of G is a set of edges so that every vertex of G is adjacent to (or covered by) at least one edge in this set. Initially all vertices of the graph are uncovered and at each step we pick a random edge among all edges and we cover its two vertices. Let τ_{G} be the edge cover time, i.e., the random variable that counts the number of steps required to cover all vertices of G. What is its expected value E[τ_{G}]?

Let C(G, k) be the number of edge coverings of G with exactly k edges. Then the probability that at the n-th step the whole graph is covered is given by

p(n) = ∑_{k=1}^{M} C(G, k)\left\{{n \atop k}\right\}\frac{k!}{M^{n}} .

Since the following identity holds

\left\{{n \atop k}\right\}k! = ∑_{r=1}^{k}(−1)^{k−r}\binom{k}{r}r^{n},

then

p(n) = ∑_{r=1}^{M} Ĉ(G, r) (\frac{r}{M} )^{n}

where

Ĉ(G, r) = ∑_{k=r}^{M}(−1)^{k−r}\binom{k}{r}C(G, k).

The probability generating function is

P (x) = ∑_{n=1}^{∞} p(n)x^{n} = ∑_{r=1}^{M} Ĉ(G, r) ∑_{n=1}^{∞} (\frac{rx}{M})^{n} = ∑_{r=1}^{M−1} Ĉ(G, r)\frac{rx}{M − rx} + \frac{x}{1 − x}

because Ĉ(G, M) = C(G, M) = 1. In order to compute E[τ_{G}] we define

Q(x) = ∑_{n=2}^{∞}(p(n) − p(n − 1))x^{n} + p(1)x = P (x)(1 − x).

Then

Q′(x) = P′(x)(1 − x) − P (x)
= (∑_{r=1}^{M−1} Ĉ(G, r)\frac{Mr}{(M − rx)^{2}} + \frac{1}{(1 − x)^{2}} ) (1 − x) − ∑_{r=1}^{M−1} Ĉ(G, r)\frac{rx}{M − rx} − \frac{x}{1 − x}

= (∑_{r=1}^{M−1} Ĉ(G, r)\frac{Mr}{(M − rx)^{2}} ) (1 − x) − ∑_{r=1}^{M−1} Ĉ(G, r)\frac{rx}{M − rx} + 1.

Finally we are able to express the answer in finite terms (see [6]) and we obtain

E[τ_{G}] = Q′(1) = 1 − ∑_{r=1}^{M−1} Ĉ(G, r)\frac{r}{M − r}.  (1)

In the next sections we will apply the above formula to several kind of graphs, after the generating function whose coefficients give C(G, k) has been determined. We decided to consider only regular graphs, so that no vertex is privileged with respect to the others.

Before we start, we would like to establish some bounds for E[τ_{G}] when G is a generic d-regular graph with N vertices (and dN/2 edges). Since the graph is regular, at each step every vertex has the same probability to be covered. Hence if we assume that only one vertex of the chosen edge is covered, then the modified process is just the classical coupon collector’s problem, and therefore its mean cover time NH_{N} is greater than E[τ_{G}]. A more precise asymptotic bound is given by the following theorem, which uses the probabilistic method (see, for example, [2]) .

Theorem 1.1. Let G be a d-regular graph with N vertices and let τ_{G} its cover time. Then for any α > 0

Pr (|\frac{τ_{G} − (N log N)/2}{N}| ≤ α) ≥ 1 − 2e^{−2α} + o(1).  (2)

Moreover,

E[τ_{G}] ∼ (N log N)/2.  (3)

Proof. Let A(v) be the event such that the vertex v is not covered after

f(N) = N(log N + a)/2

steps with a ∈ ℝ. Since the probability that the vertex v is covered at any step is

p = d/(Nd/2) = 2/N,

it follows that

Pr(A(v)) = ∑_{k>f(N)}(1 − p)^{k−1}p = (1 − p)^{f(N)} = \frac{e^{−a}}{N} + o(1/N).

If v ≠ w and v − w is not an edge, then the probability that v or w are covered at any step is

p = 2d/(Nd/2) = 4/N.

Hence

Pr(A(v) ∩ A(w)) = (1 − p)^{f(N)} = \frac{e^{−2a}}{N^{2}} + o(1/N^{2}).

On the other hand, if v ≠ w and v − w is an edge then the probability that v or w are covered at any step is

p = (2d − 1)/(Nd/2) = 4/N − 2/(Nd)

then

Pr(A(v) ∩ A(w)) = (1 − p)^{f(N)} = \frac{e^{−a(2−1/d)}}{N^{2−1/d}} + o(1/N^{2−1/d}).

Let X(v) be the indicator for the event A(v) and let X = ∑_{v} X(v) be the number of vertices v such that A(v) occurs. We have the following estimates:

E[X(v)] = 1 · Pr(A(v)) = \frac{e^{−a}}{N} + o(1/N),
Var[X(v)] = E[(X(v)]^{2}) − E[X(v)]^{2} = \frac{e^{−a}}{N} + o(1/N),
Cov[X(v), X(w)] = E[X(v) · X(w)] − E[X(v)] · E[X(w)]
= Pr(A(v) ∩ A(w)) − \frac{e^{−2a}}{N^{2}} + o(1/N^{2})

= \{ \begin{matrix}o(1/N^{2}), & if v − w is not an edge; \\ \frac{e^{−a(2−1/d)}}{N^{2−1/d}} + o(1/N^{2−1/d}), & if v − w is not an edge. \end{matrix}

Therefore

E[X] = ∑_{v} E[X(v)] = e^{−a} + o(1),
Var[X] = ∑_{v} Var[X(v)] + ∑_{v≠w} Cov[X(v), X(w)]

= e^{−a} + o(1) + Nd (\frac{e^{−a(2−1/d)}}{N^{2−1/d}} + o(1/N^{2−1/d}))
+N(N − 1 − d)o(1/N^{2})
= e^{−a} + o(1).

So we can find an explicit upper and lower bound for Pr(X = 0), that is, the the probability that the cover time τ_{G} is less than N(log N + a)/2. By Chebyshev’s inequality,

Pr(X = 0) ≤ Pr(|X − E[X]| ≥ E[X]) ≤ \frac{Var[X]}{(E[X])^{2}} = \frac{e^{−a} + o(1)}{e^{−2a} + o(1)} = e^{a} + o(1).  (4)

On the other hand

Pr(X = 0) = 1 − Pr(X > 0) ≥ 1 − E[X] = 1 − e^{−a} + o(1).  (5)

Let α > 0. By (4), if a = −2α then

Pr(τ_{G} − (N log N)/2 < −αN) ≤ e^{−2α} + o(1).

By (5), if a = 2M then

Pr(τ_{G} − (N log N)/2 > αN) = 1 − Pr(τ_{G} − (N log N)/2 < αN) ≤ e^{−2α} + o(1).

Finally

Pr(|τ_{G} − (N log N)/2| < αN) = 1 − Pr(τ_{G} − (N log N)/2 < −αN)
−Pr(τ_{G} − (N log N)/2 > αN)
≥ 1 − 2e^{−2α} + o(1)

and Eq. (2) has been proved. Eq. (3) follows directly from (2).

2 The cycle graph C_{n}

The cycle C_{n} is a 2-regular graph with N = n vertices placed around a circle and M = n edges. In order to compute the number of ways C(C_{n}, k, v) such that k edges cover v vertices of C_{n}, we choose one of the n vertices and, from there, we place clockwise the v −k connected components. Let x_{i} ≥ 1 be number of edges of the ith-component then these numbers solve the equation

x_{1} + x_{2} + ⋯ + x_{v−k} = k.

Let y_{i} ≥ 1 be number of edges of the gap between ith-component and the next one then these numbers solve equation

y_{1} + y_{2} + ⋯ + y_{v−k} = n − k.

y_{2} x_{3} x_{2}  y_{3} y_{1} x_{1}

Hence n times the number of the all positive integral solutions of the previous equations gives v − k times (the first component is labeled) the number C(C_{n}, k, v). Therefore

C(C_{n}, k, v) = \frac{n}{v − k} \binom{k − 1}{v − k − 1}\binom{n − k − 1}{v − k − 1} = \frac{n}{k}\binom{k}{v − k}\binom{n − k − 1}{v − k − 1}

and the number of edge coverings with k edges is

C(C_{n}, k) = C(C_{n}, k, n) = \frac{n}{k}\binom{k}{n − k} = [x^{n}y^{k}]\frac{2 − xy}{1 − yx − yx^{2}} .

The sequence is triangular with respect to the double index (n, k) since C(C_{n}, k) can be considered zero when k > n, and it appears in Sloane’s Encyclopedia [7] as \underline{A113214}.

It is interesting to note that the total number of edge coverings of C_{n} is the n-th Lucas number (\underline{A000032})

C(C_{n}) = ∑_{k=1}^{n} C(C_{n}, k) = ∑_{k=1}^{n} \frac{n}{k}\binom{k}{n − k} = L_{n}.

This is not a real surprise because the edge coverings of C_{n} are in bijective correpondence with the monomer-dimer tilings (no overlapping) of C_{n}: replace any vertex covered by two edges with a monomer and then fill the rest with dimers.

The following identities are well known (see, for example, [5]) and we include the proofs here for completeness.

Lemma 2.1. i) For any positive integer n

1 − n ∑_{r=1}^{n−1} \frac{(−1)^{r}}{r} \binom{n − 1}{r} = nH_{n}.  (6)

ii) For any positive integers n and p

∑_{r=p}^{n−1} \frac{(−1)^{r−p}}{r} \binom{n − 1 − p}{r − p} = \frac{1}{p\binom{n−1}{p}}  (7)

Proof. As regards identity (6)

∫_{0}^{1} \frac{(1 − x)^{n−1} − 1}{x} dx = ∫_{0}^{1} ∑_{r=1}^{n−1}(−1)^{r}\binom{n − 1}{r}x^{r−1} dx = ∑_{r=1}^{n−1} \frac{(−1)^{r}}{r} \binom{n − 1}{r},

and

∫_{0}^{1} \frac{(1 − x)^{n−1} − 1}{x} dx = − ∫_{0}^{1} \frac{t^{n−1} − 1}{t − 1} dx = − ∫_{0}^{1} ∑_{r=0}^{n−2} t^{r} dt = −H_{n−1}.

Now identity (7),

∫_{0}^{1} x^{p−1}(1−x)^{n−1−p} dx = ∫_{0}^{1} x^{p−1} ∑_{r=p}^{n−1}(−1)^{r−p}\binom{n − 1 − p}{r − p}x^{r−p} dx = ∑_{r=p}^{n−1} \frac{(−1)^{r−p}}{r} \binom{n − 1 − p}{r − p},

and on the other hand

∫_{0}^{1} x^{p−1}(1 − x)^{n−1−p} dx = B(p − 1, n − 1 − p) = \frac{(p − 1)!(n − 1 − p)!}{(n − 1)!} = \frac{1}{p\binom{n−1}{p}}.

We are now able to find an explicit formula for the mean cover time for the cycle graph. Theorem 2.2.

E[τ_{C_{n}}] = nH_{n} − n ∑_{p=1}^{⌊n/2⌋} \frac{\binom{n−p}{p}}{p\binom{n−1}{p−1}}.

Proof. By (1)

E[τ_{C_{n}}] = 1 − ∑_{r=1}^{n−1} Ĉ(C_{n}, r)\frac{r}{n − r} = 1 − ∑_{r=1}^{n−1} Ĉ(C_{n}, n − r)\frac{n − r}{r}

= 1 − ∑_{r=1}^{n−1} \frac{n − r}{r} ∑_{k=n−r}^{n}(−1)^{k−n+r}\binom{k}{n − r}\frac{n}{k}\binom{k}{n − k}

= 1 − n ∑_{r=1}^{n−1} \frac{1}{r} ∑_{k=n−r}^{n}(−1)^{k−n+r}\binom{k − 1}{n − r − 1}\binom{k}{n − k}

= 1 − n ∑_{r=1}^{n−1} \frac{1}{r} ∑_{p=0}^{r}(−1)^{r−p}\binom{n − p − 1}{r − p}\binom{n − p}{p}

= 1 − n ∑_{r=1}^{n−1} \frac{(−1)^{r}}{r} \binom{n − 1}{r} − n ∑_{p=1}^{n−1} \binom{n − p}{p} ∑_{r=p}^{n−1} \frac{(−1)^{r−p}}{r} \binom{n − p − 1}{r − p}.

Therefore, by the previous lemma

E[τ_{C_{n}}] = nH_{n} − n ∑_{p=1}^{n−1} \frac{\binom{n−p}{p}}{p\binom{n−1}{p}} = nH_{n} − n ∑_{p=1}^{⌊n/2⌋} \frac{\binom{n−p}{p}}{p\binom{n−1}{p}}.

The exact values of E[τ_{C_{n}}] for N = n = 2, 3, 4, 5, 6, 7, 8 are

1, \frac{5}{2}, \frac{11}{3}, \frac{31}{6}, \frac{67}{10}, \frac{167}{20}, \frac{151}{15}.

3 The cyclic ladder C_{n} × K_{2}

The cyclic ladder is a 3-regular graph obtained by taking the graph cartesian product of the cycle graph C_{n} and the complete graph K_{2}. It has N = 2n vertice (n on the outer circle and n in the inner circle) and M = 3n edges (n on each circle and the n rungs).

The number of coverings of C_{n} × K_{2} without rungs is L_{n}^{2} because the inner and the outer circles are covered independently. Assume that the covering has r ≥ 1 rungs then we label the first one and we let x_{i} + 1 ≥ 1 be the number of edges (on one circle) between the i-th rung and the next one. Since the number of coverings of a linear graph with x_{i} + 2 vertices with the end vertices already covered is the Fibonacci number F_{x_{i}+3} (just the number of monomer-dimer tilings of the (x_{i} + 2)-strip) then the number of coverings with r ≥ 1 rungs is given by the r-convolution

(n/r) ∑_{x_{1}+···+x_{r}=n−r} ∏_{i=1}^{r} F_{x_{i}+3}^{2} .

Therefore

C(C_{n} × K_{2}) = L_{n}^{2} + ∑_{r=1}^{n}(n/r) ∑_{x_{1}+···+x_{r}=n−r} ∏_{i=1}^{r} F_{x_{i}+3}^{2} .

Now it is easy to find the generating function: since

h(x) = ∑_{n=0}^{∞} L_{n}^{2}x^{n} = \frac{4 − 7x − x^{2}}{(1 + x)(1 − 3x + x^{2})} and g(x) = ∑_{n=0}^{∞} F_{n+3}^{2}x^{n} = \frac{4 + x − x^{2}}{(1 + x)(1 − 3x + x^{2})},

it follows that

f(x) = h(x) + (xD) (∑_{r=1}^{∞} \frac{(xg(x))^{r}}{r} ) = h(x) + (xD) (log (\frac{1}{1 − xg(x)}))

= \frac{4 − 15x − 18x^{2} − x^{3}}{(1 + x)(1 − 6x − 3x^{2} + 2x^{3})}
= 4 + 5x + 43x^{2} + 263x^{3} + 1699x^{4} + 10895x^{5} + 69943x^{6} + 448943x^{7} + o(x^{7})

and C(C_{n} × K_{2}) = [x^{n}]f(x) is the sequence \underline{A123304}.

Letting

h(x, y) = \frac{4 − (4y + 3y^{2})x − y^{3}x^{2}}{1 − (y + y^{2})x − (y^{2} + y^{3})x^{2} + y^{3}x^{3}}

and

g(x) = \frac{1 + 2y + y^{2} + (−y + y^{2} + y^{3})x − y^{3}x^{2}}{1 − (y + y^{2})x − (y^{2} + y^{3})x^{2} + y^{3}x^{3}} ,

by a similar argument, we can show that C(C_{n} × K_{2}, k) = [x^{n}y^{k}]f(x, y) where

f(x, y) = h(x, y) + (x\frac{∂}{∂x}) (log (\frac{1}{1 − xyg(x, y)}))
= \frac{4 − (3y + 9y^{2} + 3y^{3})x − (4y^{2} + 10y^{3} + 4y^{4})x^{2} + (y^{3} − y^{4} − y^{5})x^{3}}{(1 + xy)(1 − (2y + 3y^{2} + y^{3})x − (2y^{3} + y^{4})x^{2} + (y^{3} + y^{4})x^{3})} .

By (1), the exact values of E[τ_{C_{n}×K_{2}}] for N = 2n = 4, 6, 8, 10 are

\frac{18}{5}, \frac{1919}{280}, \frac{788}{77}, \frac{334283}{24024}.

4 K_{n} and K_{n,n}

There are two other important regular graphs whose edge coverings are counted by sequences contained in the Sloane’s Encyclopedia [7]: the complete graph K_{n} and the complete bipartite graph K_{n,n}. All the formulas can be verified by applying the inclusion-exclusion principle. The triangular sequence C(K_{n}, k) for 0 ≤ k ≤ M = \binom{n}{2} is \underline{A054548} and C(K_{n}) is \underline{A006129}:

C(K_{n}, k) = ∑_{j=0}^{n}(−1)^{j}\binom{n}{j}\binom{\binom{n−j}{2}}{k} and C(K_{n}) = ∑_{j=0}^{n}(−1)^{j}\binom{n}{j}2^{\binom{n−j}{2}}.

By (1), the exact values of E[τ_{K_{n}}] for N = n = 2, 3, 4, 5, 6 are

1, \frac{5}{2}, \frac{19}{5}, \frac{671}{126}, \frac{97}{14}.

The triangular sequence C(K_{n,n}, k) for 0 ≤ k ≤ M = n^{2} is \underline{A055599} and C(K_{n,n}) is \underline{A048291}

C(K_{n,n}, k) = ∑_{i=0}^{n}(−1)^{i}\binom{n}{i} ∑_{j=0}^{n}(−1)^{j}\binom{n}{j}\binom{(n − j)(n − i)}{k}

and

C(K_{n,n}) = ∑_{j=0}^{n}(−1)^{j}\binom{n}{j}(2^{n−j} − 1)^{n}.

By (1), the exact values of E[τ_{K_{n,n}}] for N = 2n = 2, 4, 6, 8, 10 are

1, \frac{11}{3}, \frac{1909}{280}, \frac{4687}{455}, \frac{144789}{10313}.

References

[1] M. Adler, E. Halperin, R. Karp and V. Vazirani, A stochastic process on the hypercube with applications to peer-to-peer networks, Proc. STOC 2003, 575–584.

[2] N. Alon and J. H. Spencer, The Probabilistic Method, 2nd Edition, Wiley, 2000.

[3] C. Cooper and A. Frieze, The cover time of random regular graphs, SIAM J. Discrete Math., 18 (2005), 728–740.

[4] N. Dimitrov and C. Plaxton, Optimal cover time for a graph-based coupon collector process, Proc. ICALP 2005, 702–716.

[5] H. W. Gould, Combinatorial Identities, Morgantown, West Virginia, 1972.

[6] A. N. Myers and H. Wilf, Some new aspects of the coupon collector’s problem, SIAM J. Discrete Math., 17 (2003), 1–17.

[7] N. J. A. Sloane, The On-Line Encyclopedia of Integer Sequences, published electronically at http://www.research.att.com/∼njas/sequences/.

2000 Mathematics Subject Classification: Primary 60C05. Keywords: coupon collector’s problem, graph, edge cover.

(Concerned with sequences \underline{A000032}, \underline{A006129}, \underline{A048291}, \underline{A054548}, \underline{A055599}, \underline{A113214}, and \underline{A123304}.)

Received October 23 2006; revised version received May 24 2008; September 30 2008. Published in Journal of Integer Sequences, October 4 2008.

Return to Journal of Integer Sequences home page.