Cover time of a random graph with given degree sequence
type: Item
instance of: scholarly article
title: Cover time of a random graph with given degree sequence
zbMATH Open document ID: 1252.05207
author: Colin Cooper
author: Mohammed Abdullah
author: Alan Frieze
published in: Discrete Mathematics
publication date: 2012-10-16T00:00:00Z
review text: The authors study the cover time of a graph chosen uniformly at random from the set of \(n\)-vertex graphs with a given degree sequence \(\mathbf{d}\). They obtain an asymptoticly exact result which holds with high probability (as \(n\rightarrow\infty\)) for degree sequences \(\mathbf{d}\) satisfying certain restrictions, most notable of them that the average degree is \(o(\sqrt{\log n})\). More precisely, they prove that under these conditions, the cover time of a typical random graph with degree sequence \(\mathbf{d}\) is asymptotically \(\frac{d-1}{d-2}\frac{\theta}{d}n\log n\). Here, \(\theta\) is the average degree, and \(d\) is the ``effective minimum degree'' of \(\mathbf{d}\), i.e., the smallest \(d\) such that \(G\) contains a vanishing proportion of vertices of degrees \(d-1,d-2,\dots\).
reviewed by: Jan Hladký
Mathematics Subject Classification ID: 05C81
Mathematics Subject Classification ID: 05C80
Mathematics Subject Classification ID: 05C07
zbMATH DE Number: 6093928
zbMATH Keywords: cover time
zbMATH Keywords: random graphs
zbMATH Keywords: degree sequence
zbMATH Keywords: random walks on graphs
Wikidata QID: Q57401437
MaRDI profile type: Publication
full work available at URL: j.disc.2012.07.006
OpenAlex ID: W3022880991
cites work: A probabilistic proof of an asymptotic formula for the number of labelled regular graphs
cites work: The Cover Time of Random Regular Graphs
cites work: The cover time of the giant component of a random graph
cites work: Q3706275
cites work: A tight lower bound on the cover time for random walks on graphs
cites work: A tight upper bound on the cover time for random walks on graphs
cites work: Asymptotic enumeration by degree sequence of graphs with degrees \(o(n^{1/2})\)
cites work: Improved Bounds for Mixing Rates of Markov Chains and Multicommodity Flow
cites work: Q3995745
DOI: 10.1016/J.DISC.2012.07.006
DBLP publication ID: journals/dm/AbdullahCF12
description: scientific article; zbMATH DE number 6093928