\documentclass[12pt,reqno]{article} \usepackage{pst-node,graphics} \newpsobject{showgrid}{psgrid}{subgriddiv=1,griddots=10,gridlabels=6pt} \usepackage[colorlinks=true,linkcolor=webgreen, filecolor=webbrown,citecolor=webgreen]{hyperref} \usepackage{amsthm,amssymb,color,epsf} \usepackage[usenames]{color} \usepackage{graphicx} \usepackage{amscd} \definecolor{webgreen}{rgb}{0,.5,0} \definecolor{webbrown}{rgb}{.6,0,0} \usepackage{color} \usepackage{fullpage} \usepackage{float} \usepackage{psfig} \usepackage{graphics,amsmath,amssymb} \usepackage{amsthm} \usepackage{amsfonts} \usepackage{latexsym} \usepackage{epsf} \setlength{\textwidth}{6.5in} \setlength{\oddsidemargin}{.1in} \setlength{\evensidemargin}{.1in} \setlength{\topmargin}{-.5in} \setlength{\textheight}{8.9in} \newcommand{\seqnum}[1]{\href{http://www.research.att.com/cgi-bin/access.cgi/as/~njas/sequences/eisA.cgi?Anum=#1}{\underline{#1}}} \begin{document} \newtheorem{theorem}{Theorem} \newtheorem{corollary}[theorem]{Corollary} \newtheorem{lemma}[theorem]{Lemma} \newtheorem{proposition}[theorem]{Proposition} \newtheorem{conjecture}[theorem]{Conjecture} \newtheorem{Definition}{Definition}[section] \newtheorem{Lemma}[Definition]{Lemma} \newtheorem{Theorem}[Definition]{Theorem} \newtheorem{Notation}[Definition]{Notation} \newtheorem{Prop}[Definition]{Proposition} \newtheorem{Cor}[Definition]{Corollary} \newtheorem{Conj}[Definition]{Conjecture} %\makeatletter %\def\section{\@startsection {section}{1}{\z@}{-3.5ex plus -1ex minus % -.2ex}{2.3ex plus .2ex}{\normalsize\bf}} %\makeatother \newcommand{\st}[2]{\genfrac{\{}{\}}{0pt}{}{#1}{#2}} %%%%%%%%%%%%%%%%%%%%% %Simboli \def\RR{{\mathbb R}} \def\CC{{\bf C}} \def\Rd{{\bf R}^2} \def\Rt{{\bf R}^3} \def\Rn{\RR^n} \def\GG{{\cal G}} \def\CC{{\cal C}} \def\KK{{\cal K}} \def\wC{{\widehat{C}}} \def\Pr{\mbox{Pr}} \newgray{mygray}{0.8} \def\vb{\psellipse[fillstyle=solid,fillcolor=black](0,0)(0.1,0.1)} \def\vl{\psellipse[linewidth=0.05, fillstyle=solid,fillcolor=white](0,0)(0.1,0.1)} \def\vg{\psellipse[linecolor=mygray,fillstyle=solid,fillcolor=mygray](0,0)(0.1,0.1)} \begin{center} \epsfxsize=4in \leavevmode\epsffile{logo129.eps} \end{center} \begin{center} \vskip 1cm {\LARGE\bf Edge Cover Time for Regular Graphs} \\ \vskip 1cm \large Roberto Tauraso \\ Dipartimento di Matematica \\ Universit\`a di Roma ``Tor Vergata'' \\ via della Ricerca Scientifica\\ 00133 Roma\\ Italy\\ \href{mailto:tauraso@mat.uniroma2.it}{\tt tauraso@mat.uniroma2.it} \end{center} \vskip 1cm \begin{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. \end{abstract} \theoremstyle{plain} \newtheorem{mainthm}{Theorem} \newtheorem{bigthm}{Theorem} \newtheorem{thm}{Theorem}[section] \newtheorem{prop}[thm]{Proposition} \newtheorem{lem}[thm]{Lemma} \newtheorem{cor}[thm]{Corollary} \newtheorem{defn}[thm]{Definition} \newtheorem{defs}[thm]{Definitions} \newtheorem{example}[thm]{Example} \theoremstyle{remark} \newtheorem*{remark}{Remark} \begin{section}{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, \cite{AHKV,AS,CF,DP}) 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 $\GG$ be a connected graph with $N\geq 2$ vertices and $M\geq 1$ edges (no loops). An {\sl edge covering} of $\GG$ is a set of edges so that every vertex of $\GG$ is adjacent to (or {\sl 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 $\tau_{\GG}$ be the {\sl 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[\tau_{\GG}]$? Let $C(\GG,k)$ be the number of edge coverings of $\GG$ with exactly $k$ edges. Then the probability that at the $n$-th step the whole graph is covered is given by $$p(n)=\sum_{k=1}^{M} C(\GG,k) \st{n}{k} {k! \over M^n}.$$ Since the following identity holds $$\st{n}{k}k!=\sum_{r=1}^{k}(-1)^{k-r}{k \choose r}r^n,$$ then $$p(n)=\sum_{r=1}^{M} \wC(\GG,r) \left({r \over M}\right)^n$$ where $$\wC(\GG,r)=\sum_{k=r}^{M} (-1)^{k-r} {k \choose r} C(\GG,k).$$ The probability generating function is $$P(x)=\sum_{n=1}^{\infty}p(n) x^n=\sum_{r=1}^{M}\wC(\GG,r)\sum_{n=1}^{\infty} \left({r x\over M}\right)^n =\sum_{r=1}^{M-1}\wC(\GG,r){rx\over M-rx}+{x\over 1-x} $$ because $\wC(\GG,M)=C(\GG,M)=1$. In order to compute $E[\tau_{\GG}]$ we define $$Q(x)=\sum_{n=2}^{\infty}(p(n)-p(n-1)) x^n+p(1)x=P(x)(1-x).$$ Then \begin{eqnarray*} Q'(x)&=&P'(x)(1-x)-P(x)\\ &=& \left(\sum_{r=1}^{M-1}\wC(\GG,r){Mr\over (M-rx)^2}+{1\over (1-x)^2}\right)(1-x)- \sum_{r=1}^{M-1}\wC(\GG,r){rx\over M-rx}-{x\over 1-x}\\ &=& \left(\sum_{r=1}^{M-1}\wC(\GG,r){Mr\over (M-rx)^2}\right)(1-x)-\sum_{r=1}^{M-1}\widehat{C}(\GG,r){rx\over M-rx}+1. \end{eqnarray*} Finally we are able to express the answer in finite terms (see \cite{MW}) and we obtain \begin{equation}\label{eq99} E[\tau_{\GG}]=Q'(1)=1-\sum_{r=1}^{M-1}\wC(\GG,r){r\over M-r}. \end{equation} In the next sections we will apply the above formula to several kind of graphs, after the generating function whose coefficients give $C(\GG,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[\tau_{\GG}]$ when $\GG$ 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[\tau_{\GG}]$. A more precise asymptotic bound is given by the following theorem, which uses the probabilistic method (see, for example, \cite{AS}) . \begin{Theorem} Let $\GG$ be a $d$-regular graph with $N$ vertices and let $\tau_{\GG}$ its cover time. Then for any $\alpha>0$ \begin{equation}\label{eq100} \Pr\left(\left|{\tau_{\GG}-(N\log N)/2\over N}\right|\leq \alpha\right)\geq 1-2e^{-2\alpha}+o(1) . \end{equation} Moreover, \begin{equation}\label{eq101} E[\tau_{\GG}]\sim (N\log N)/2. \end{equation} \end{Theorem} \begin{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\in\RR$. 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))=\sum_{k>f(N)}(1-p)^{k-1}p=(1-p)^{f(N)}={e^{-a}\over N}+o(1/N).$$ If $v\not=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)\cap A(w))=(1-p)^{f(N)}={e^{-2a}\over N^2}+o(1/N^2).$$ On the other hand, if $v\not=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)\cap A(w))=(1-p)^{f(N)}={e^{-a(2-1/d)}\over N^{2-1/d}}+o(1/N^{2-1/d}).$$ Let $X(v)$ be the indicator for the event $A(v)$ and let $X=\sum_{v} X(v)$ be the number of vertices $v$ such that $A(v)$ occurs. We have the following estimates: \begin{eqnarray*} E[X(v)]&=&1\cdot \Pr(A(v))={e^{-a}\over N}+o(1/N),\\ {\rm Var}[X(v)]&=& E[(X(v)]^2)-E[X(v)]^2={e^{-a}\over N}+o(1/N),\\ {\rm Cov}[X(v),X(w)]&=& E[X(v)\cdot X(w)]-E[X(v)]\cdot E[X(w)]\\ &=&\Pr(A(v)\cap A(w))-{e^{-2a}\over N^2}+o(1/N^2)\\ &=&\left\{ \begin{array}{ll}\displaystyle o(1/N^2),&\mbox{if $v-w$ is not an edge;}\\\displaystyle {e^{-a(2-1/d)}\over N^{2-1/d}}+o(1/N^{2-1/d}),&\mbox{if $v-w$ is not an edge.} \end{array} \right. \end{eqnarray*} Therefore \begin{eqnarray*} E[X]&=&\sum_{v} E[X(v)]=e^{-a}+o(1),\\ {\rm Var}[X]&=&\sum_{v} {\rm Var}[X(v)]+\sum_{v\not= w} {\rm Cov}[X(v),X(w)]\\ &=&e^{-a}+o(1)+Nd\left({e^{-a(2-1/d)}\over N^{2-1/d}}+o(1/N^{2-1/d})\right)\\ &&+N(N-1-d)o(1/N^2)\\ &=&e^{-a}+o(1). \end{eqnarray*} So we can find an explicit upper and lower bound for $\Pr(X=0)$, that is, the the probability that the cover time $\tau_{\GG}$ is less than $N(\log N+a)/2$. By Chebyshev's inequality, \begin{equation}\label{eq200} \Pr(X=0)\leq \Pr(|X-E[X]|\geq E[X])\leq {{\rm Var}[X]\over (E[X])^2}={e^{-a}+o(1)\over e^{-2a}+o(1)}=e^a+o(1). \end{equation} On the other hand \begin{equation}\label{eq201} \Pr(X=0)=1-\Pr(X>0)\geq 1-E[X]=1-e^{-a}+o(1). \end{equation} Let $\alpha>0$. By (\ref{eq200}), if $a=-2\alpha$ then $$\Pr(\tau_{\GG}-(N\log N)/2< -\alpha N)\leq e^{-2\alpha}+o(1).$$ By (\ref{eq201}), if $a=2M$ then $$\Pr(\tau_{\GG}-(N\log N)/2> \alpha N)=1-\Pr(\tau_{\GG}-(N\log N)/2<\alpha N)\leq e^{-2\alpha}+o(1).$$ Finally \begin{eqnarray*} \Pr(|\tau_{\GG}-(N\log N)/2|< \alpha N)&=&1-\Pr(\tau_{\GG}-(N\log N)/2< -\alpha N)\\ &&-\Pr(\tau_{\GG}-(N\log N)/2>\alpha N)\\ &\geq& 1-2e^{-2\alpha}+o(1) \end{eqnarray*} and Eq.~(\ref{eq100}) has been proved. Eq.~(\ref{eq101}) follows directly from (\ref{eq100}). \end{proof} \end{section} \begin{section}{The cycle graph $\CC_n$} The cycle $\CC_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(\CC_n,k,v)$ such that $k$ edges cover $v$ vertices of $\CC_n$, we choose one of the $n$ vertices and, from there, we place clockwise the $v-k$ connected components. Let $x_i\geq 1$ be number of edges of the $i$th-component then these numbers solve the equation $$x_1+x_2+\cdots+x_{v-k}=k.$$ Let $y_i\geq 1$ be number of edges of the gap between $i$th-component and the next one then these numbers solve equation $$y_1+y_2+\cdots+y_{v-k}=n-k.$$ \begin{center} \begin{pspicture}(-2,-2.5)(2,2.5) %\showgrid \psarc[linecolor=black](0,0){2}{0}{45} \psarc[linecolor=mygray](0,0){2}{45}{90} \psarc[linecolor=black](0,0){2}{90}{135} \psarc[linecolor=black](0,0){2}{135}{180} \psarc[linecolor=mygray](0,0){2}{180}{225} \psarc[linecolor=black](0,0){2}{225}{270} \psarc[linecolor=mygray](0,0){2}{270}{315} \psarc[linecolor=mygray](0,0){2}{315}{360} \psline(1.4142,1.4142)(1.8,1.8) \psarc[linestyle=dashed]{<->}(0,0){2.25}{0}{45}\rput(2.3097,0.9567){$x_1$} \psarc[linestyle=dashed]{<->}(0,0){2.25}{45}{90}\rput(0.9567,2.3097){$y_3$} \psarc[linestyle=dashed]{<->}(0,0){2.25}{90}{180}\rput(-1.7678,1.7678){$x_3$} \psarc[linestyle=dashed]{<->}(0,0){2.25}{180}{225}\rput(-2.3097,-0.9567){$y_2$} \psarc[linestyle=dashed]{<->}(0,0){2.25}{225}{270}\rput(-0.9567,-2.3097){$x_2$} \psarc[linestyle=dashed]{<->}(0,0){2.25}{270}{0}\rput(1.7678,-1.7678){$y_1$} %%%%%%%%%%%%%%%%%%%% \put(2,0){\vb} \put(0,2){\vb} \put(-2,0){\vb} \put(0,-2){\vb} \put(1.4142,1.4142){\vb} \put(-1.4142,1.4142){\vb} \put(1.4142,-1.4142){\vg} \put(-1.4142,-1.4142){\vb} \end{pspicture} \end{center} 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(\CC_n,k,v)$. Therefore $$C(\CC_n,k,v)={n\over v-k}{k-1 \choose v-k-1 }{n-k-1 \choose v-k-1 }={n\over k}{k \choose v-k}{n-k-1 \choose v-k-1 }$$ and the number of edge coverings with $k$ edges is $$C(\CC_n,k)=C(\CC_n,k,n)={n\over k}{k \choose n-k}= [x^ny^k]{2-xy\over{ 1-yx-yx^2}}.$$ The sequence is {\sl triangular} with respect to the double index $(n,k)$ since $C(\CC_n,k)$ can be considered zero when $k>n$, and it appears in Sloane's {\it Encyclopedia} \cite{Sloane} as \seqnum{A113214}. It is interesting to note that the total number of edge coverings of $\CC_n$ is the $n$-th Lucas number (\seqnum{A000032}) $$C(\CC_n)=\sum_{k=1}^{n}C(\CC_n,k)=\sum_{k=1}^{n} {n\over k}{k \choose n-k}=L_n.$$ This is not a real surprise because the edge coverings of $\CC_n$ are in bijective correpondence with the monomer-dimer tilings (no overlapping) of $\CC_n$: replace any vertex covered by two edges with a monomer and then fill the rest with dimers. \begin{center} \begin{pspicture}(0,-2.5)(10,2.5) \put(2,0){ \psarc[linecolor=black](0,0){2}{0}{45} \psarc[linecolor=black](0,0){2}{45}{90} \psarc[linecolor=black](0,0){2}{90}{135} \psarc[linecolor=mygray](0,0){2}{135}{180} \psarc[linecolor=black](0,0){2}{180}{225} \psarc[linecolor=mygray](0,0){2}{225}{270} \psarc[linecolor=black](0,0){2}{270}{315} \psarc[linecolor=mygray](0,0){2}{315}{360} %%%%%%%%%%%%%%%%%%%% \put(2,0){\vb} \put(0,2){\vb} \put(-2,0){\vb} \put(0,-2){\vb} \put(1.4142,1.4142){\vb} \put(-1.4142,1.4142){\vb} \put(1.4142,-1.4142){\vb} \put(-1.4142,-1.4142){\vb} } \put(8,0){ \pscircle(0,0){1.75} \pscircle(0,0){2.25} \psline(0.6697,1.6168)(0.8610,2.0787) \psline(1.6168,0.6697)(2.0787,0.8610) %\psline(1.6168,-0.6697)(2.0787,-0.8610) \psline(0.6697,-1.6168)(0.8610,-2.0787) \psline(-0.6697,1.6168)(-0.8610,2.0787) %\psline(-1.6168,0.6697)(-2.0787,0.8610) \psline(-1.6168,-0.6697)(-2.0787,-0.8610) %\psline(-0.6697,-1.6168)(-0.8610,-2.0787) \put(2,0){\vb} \put(0,2){\vb} \put(-2,0){\vb} \put(0,-2){\vb} \put(1.4142,1.4142){\vb} \put(-1.4142,1.4142){\vb} \put(1.4142,-1.4142){\vb} \put(-1.4142,-1.4142){\vb} } %%%%%%%%%%%%%%%%%%%% %\showgrid \end{pspicture} \end{center} The following identities are well known (see, for example, \cite{G}) and we include the proofs here for completeness. \begin{Lemma} i) For any positive integer $n$ \begin{equation}\label{eq1} 1-n\sum_{r=1}^{n-1}{(-1)^r\over r}{n-1 \choose r}=nH_n. \end{equation} ii) For any positive integers $n$ and $p$ \begin{equation}\label{eq2} \sum_{r=p}^{n-1}{(-1)^{r-p}\over r}{n-1-p\choose r-p}={1\over p{n-1 \choose p}} \end{equation} \end{Lemma} \begin{proof} As regards identity (\ref{eq1}) $$\int_0^1{(1-x)^{n-1}-1 \over x}\,dx=\int_0^1\sum_{r=1}^{n-1}(-1)^r{n-1 \choose r}x^{r-1}\,dx=\sum_{r=1}^{n-1}{(-1)^r\over r}{n-1 \choose r},$$ and $$\int_0^1{(1-x)^{n-1}-1 \over x}\,dx=-\int_0^1{t^{n-1}-1 \over t-1}\,dx=-\int_0^1\sum_{r=0}^{n-2}t^r\,dt=-H_{n-1}.$$ Now identity (\ref{eq2}), $$\int_0^1 x^{p-1}(1-x)^{n-1-p}\,dx= \int_0^1 x^{p-1}\sum_{r=p}^{n-1}(-1)^{r-p} {n-1-p \choose r-p}x^{r-p}\,dx=\sum_{r=p}^{n-1}{(-1)^{r-p}\over r}{n-1-p\choose r-p},$$ and on the other hand $$\int_0^1 x^{p-1}(1-x)^{n-1-p}\,dx=B(p-1,n-1-p)={(p-1)!(n-1-p)!\over (n-1)!}={1\over p{n-1 \choose p}}.$$ \end{proof} We are now able to find an explicit formula for the mean cover time for the cycle graph. \begin{Theorem} $$E[\tau_{\CC_n}]=n H_n-n\sum_{p=1}^{\lfloor n/2 \rfloor} {{n-p \choose p}\over p{n-1 \choose p-1}}.$$ \end{Theorem} \begin{proof} By (\ref{eq99}) \begin{eqnarray*} E[\tau_{\CC_n}]&=& 1-\sum_{r=1}^{n-1}\wC(\CC_n,r){r\over n-r}=1-\sum_{r=1}^{n-1}\wC(\CC_n,n-r){n-r\over r}\\ &=& 1-\sum_{r=1}^{n-1}{n-r\over r}\sum_{k=n-r}^{n}(-1)^{k-n+r}{k\choose n-r}{n\over k}{k\choose n-k}\\ &=& 1-n\sum_{r=1}^{n-1}{1\over r}\sum_{k=n-r}^{n}(-1)^{k-n+r}{k-1\choose n-r-1}{k\choose n-k}\\ &=& 1-n\sum_{r=1}^{n-1}{1\over r}\sum_{p=0}^{r}(-1)^{r-p}{n-p-1\choose r-p}{n-p\choose p}\\ &=& 1-n\sum_{r=1}^{n-1}{(-1)^{r}\over r}{n-1\choose r} -n\sum_{p=1}^{n-1}{n-p\choose p}\sum_{r=p}^{n-1}{(-1)^{r-p}\over r}{n-p-1\choose r-p}. \end{eqnarray*} Therefore, by the previous lemma $$E[\tau_{\CC_n}]=n H_n-n\sum_{p=1}^{n-1}{{n-p \choose p}\over p{n-1 \choose p}}= n H_n-n\sum_{p=1}^{\lfloor n/2 \rfloor} {{n-p \choose p}\over p{n-1 \choose p}}.$$ \end{proof} The exact values of $E[\tau_{\CC_{n}}]$ for $N=n=2,3,4,5,6,7,8$ are $$1,{5 \over 2}, {11 \over 3}, {31 \over 6},{67 \over 10}, {167 \over 20}, {151 \over 15}.$$ \end{section} \begin{section}{The cyclic ladder $\CC_n\times \KK_2$} The cyclic ladder is a $3$-regular graph obtained by taking the graph cartesian product of the cycle graph $\CC_n$ and the complete graph $\KK_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). \begin{center} \begin{pspicture}(-2,-2)(2,2) %\psarc[linestyle=dashed]{<->}(0,0){3.3}{270}{45}\rput(3.3260,-1.3777){$x_1$} %\psarc[linestyle=dashed]{<->}(0,0){3.3}{180}{270}\rput(-2.5456,-2.5456){$x_2$} %\psarc[linestyle=dashed]{<->}(0,0){3.3}{45}{180}\rput(-1.3777,3.3260){$x_3$} %\psline(2.1213,2.1213)(2.5,2.5) %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \psarc[linecolor=mygray](0,0){1}{0}{45} \psarc[linecolor=black](0,0){1}{45}{90} \psarc[linecolor=black](0,0){1}{90}{135} \psarc[linecolor=mygray](0,0){1}{135}{180} \psarc[linecolor=black](0,0){1}{180}{225} \psarc[linecolor=black](0,0){1}{225}{270} \psarc[linecolor=mygray](0,0){1}{270}{315} \psarc[linecolor=black](0,0){1}{315}{360} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \psarc[linecolor=black](0,0){2}{0}{45} \psarc[linecolor=mygray](0,0){2}{45}{90} \psarc[linecolor=black](0,0){2}{90}{135} \psarc[linecolor=mygray](0,0){2}{135}{180} \psarc[linecolor=mygray](0,0){2}{180}{225} \psarc[linecolor=black](0,0){2}{225}{270} \psarc[linecolor=black](0,0){2}{270}{315} \psarc[linecolor=mygray](0,0){2}{315}{360} %%%%%%%%%%%%%%%%%%%% \psline[linecolor=mygray](1,0)(2,0) \put(1,0){\vb}\put(2,0){\vb} %%%%%%%%%%%%%%%%%%%%% \psline[linecolor=mygray](0,1)(0,2) \put(0,1){\vb}\put(0,2){\vb} %%%%%%%%%%%%%%%%%%%% \psline[linecolor=black](-1,0)(-2,0) \put(-1,0){\vb}\put(-2,0){\vb} %%%%%%%%%%%%%%%%%%% \psline[linecolor=black](0,-1)(0,-2) \put(0,-1){\vb}\put(0,-2){\vb} %%%%%%%%%%%%%%%%%%%%%%% \psline[linecolor=black](0.7071,0.7071)(1.4142,1.4142) \put(0.7071,0.7071){\vb}\put(1.4142,1.4142){\vb} %%%%%%%%%%%%%%%%%%%%%%% \psline[linecolor=mygray](0.7071,-0.7071)(1.4142,-1.4142) \put(0.7071,-0.7071){\vb}\put(1.4142,-1.4142){\vb} %%%%%%%%%%%%%%%%%%%%%%% \psline[linecolor=mygray](-0.7071,-0.7071)(-1.4142,-1.4142) \put(-0.7071,-0.7071){\vb}\put(-1.4142,-1.4142){\vb} %%%%%%%%%%%%%%%%%%%%%%% \psline[linecolor=mygray](-0.7071,0.7071)(-1.4142,1.4142) \put(-0.7071,0.7071){\vb}\put(-1.4142,1.4142){\vb} %\showgrid \end{pspicture} \end{center} The number of coverings of $\CC_n\times \KK_2$ without rungs is $L_n^2$ because the inner and the outer circles are covered independently. Assume that the covering has $r\geq 1$ rungs then we label the first one and we let $x_i+1\geq 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\geq 1$ rungs is given by the $r$-convolution $$(n/r)\!\!\!\!\!\!\sum_{x_1+\cdots +x_r=n-r} \;\prod_{i=1}^r F_{x_i+3}^2\;.$$ Therefore $$C(\CC_n \times \KK_2)=L_n^2+\sum_{r=1}^{n}(n/r)\!\!\!\!\!\! \sum_{x_1+\cdots +x_r=n-r} \; \prod_{i=1}^r F_{x_i+3}^2\,.$$ Now it is easy to find the generating function: since $$h(x)=\sum_{n=0}^{\infty} L_{n}^2 x^n={4-7x-x^2\over (1+x)(1-3x+x^2)} \quad\mbox{and}\quad g(x)=\sum_{n=0}^{\infty} F_{n+3}^2 x^n={4+x-x^2\over (1+x)(1-3x+x^2)},$$ it follows that \begin{eqnarray*} f(x)&=&h(x)+(xD)\left(\sum_{r=1}^{\infty}{(xg(x))^r\over r}\right)= h(x)+(xD)\left(\log\left({1 \over 1-xg(x)}\right)\right)\\ &=&{4-15x-18x^2-x^3\over (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) \end{eqnarray*} and $C(\CC_n \times \KK_2)=[x^n]f(x)$ is the sequence \seqnum{A123304}. Letting $$h(x,y)={4-(4y+3y^2)x-y^3x^2\over 1-(y+y^2)x-(y^2+y^3)x^2+y^3x^3}$$ and $$g(x)={1+2y+y^2+(-y+y^2+y^3)x-y^3x^2\over 1-(y+y^2)x-(y^2+y^3)x^2+y^3x^3},$$ by a similar argument, we can show that $C(\CC_n \times \KK_2,k)=[x^ny^k]f(x,y)$ where \begin{eqnarray*} f(x,y)&=&h(x,y)+\left(x{\partial\over \partial x}\right)\left(\log\left({1 \over 1-xyg(x,y)}\right)\right)\\ &=&{4-(3y+9y^2+3y^3)x-(4y^2+10y^3+4y^4)x^2+(y^3-y^4-y^5)x^3\over (1+xy)(1-(2y+3y^2+y^3)x-(2y^3+y^4)x^2+(y^3+y^4)x^3)} . \end{eqnarray*} By (\ref{eq99}), the exact values of $E[\tau_{\CC_n \times \KK_2}]$ for $N=2n=4,6,8,10$ are $${18 \over 5}, {1919 \over 280}, {788 \over 77}, {334283 \over 24024}.$$ \end{section} \begin{section}{$\KK_n$ and $\KK_{n,n}$} There are two other important regular graphs whose edge coverings are counted by sequences contained in the Sloane's {\it Encyclopedia} \cite{Sloane}: the complete graph $\KK_n$ and the complete bipartite graph $\KK_{n,n}$. All the formulas can be verified by applying the inclusion-exclusion principle. The triangular sequence $C(\KK_n,k)$ for $0\leq k\leq M={n\choose 2}$ is \seqnum{A054548} and $C(\KK_n)$ is \seqnum{A006129}: $$C(\KK_n,k)=\sum_{j=0}^{n}(-1)^{j}{n \choose j}{{n-j \choose 2} \choose k} \quad \mbox{and}\quad C(\KK_n)=\sum_{j=0}^{n}(-1)^{j}{n \choose j}2^{{n - j\choose 2}}.$$ By (\ref{eq99}), the exact values of $E[\tau_{\KK_n}]$ for $N=n=2,3,4,5,6$ are $$1,{5 \over 2}, {19 \over 5}, {671 \over 126}, {97 \over 14}.$$ The triangular sequence $C(\KK_{n,n},k)$ for $0\leq k\leq M=n^2$ is \seqnum{A055599} and $C(\KK_{n,n})$ is \seqnum{A048291} $$C(\KK_{n,n},k)=\sum_{i=0}^{n}(-1)^i{n \choose i}\sum_{j=0}^{n}(-1)^{j}{n \choose j}{(n-j)(n-i) \choose k}$$ and $$C(\KK_{n,n})=\sum_{j=0}^{n}(-1)^{j}{n \choose j}(2^{n-j}-1)^n.$$ By (\ref{eq99}), the exact values of $E[\tau_{\KK_{n,n}}]$ for $N=2n=2,4,6,8,10$ are $$1,{11 \over 3},{1909 \over 280},{4687 \over 455},{144789\over 10313}.$$ \end{section} \begin{thebibliography}{99} \bibitem{AHKV} M. Adler, E. Halperin, R. Karp and V. Vazirani, A stochastic process on the hypercube with applications to peer-to-peer networks, \emph{Proc. STOC 2003}, 575--584. \bibitem{AS} N. Alon and J. H. Spencer, \emph{The Probabilistic Method}, 2nd Edition, Wiley, 2000. \bibitem{CF} C. Cooper and A. Frieze, The cover time of random regular graphs, \emph{SIAM J. Discrete Math.}, \textbf{18} (2005), 728--740. \bibitem{DP} N. Dimitrov and C. Plaxton, Optimal cover time for a graph-based coupon collector process, \emph{Proc. ICALP 2005}, 702--716. \bibitem{G} H. W. Gould, \emph{Combinatorial Identities}, Morgantown, West Virginia, 1972. \bibitem{MW} A. N. Myers and H. Wilf, Some new aspects of the coupon collector's problem, \emph{SIAM J. Discrete Math.}, \textbf{17} (2003), 1--17. \bibitem{Sloane} N. J. A. Sloane, \emph{The On-Line Encyclopedia of Integer Sequences}, published electronically at \htmladdnormallink{http://www.research.att.com/$\sim $njas/sequences/}{http://www.research.att.com/~njas/sequences/}. \end{thebibliography} \bigskip \hrule \bigskip \noindent 2000 {\it Mathematics Subject Classification}: \ \ Primary 60C05. \noindent \emph{Keywords:} coupon collector's problem, graph, edge cover. \bigskip \hrule \bigskip \noindent (Concerned with sequences \seqnum{A000032}, \seqnum{A006129}, \seqnum{A048291}, \seqnum{A054548}, \seqnum{A055599}, \seqnum{A113214}, and \seqnum{A123304}.) \bigskip \hrule \bigskip \vspace*{+.1in} \noindent Received October 23 2006; revised version received May 24 2008; September 30 2008. Published in {\it Journal of Integer Sequences}, October 4 2008. \bigskip \hrule \bigskip \noindent Return to \htmladdnormallink{Journal of Integer Sequences home page}{http://www.math.uwaterloo.ca/JIS/}. \vskip .1in \end{document}