Skip to main contentSkip to search
Episciences
Open Access Journals
Sign in(new window)
Discrete Mathematics & Theoretical Computer Science logo
Discrete Mathematics & Theoretical Computer Science
Discrete Mathematics & Theoretical Computer Science logo
Discrete Mathematics & Theoretical Computer Science
Sign in(new window)
Articles & Issues
All articlesAll accepted articlesAll volumesLast volumeSectionsSpecial issuesAuthors
About
The journalIndexing
Boards
Publish
For authorsEthical charter
Submit
Discrete Mathematics & Theoretical Computer Science logo
Contact
|
Credits
eISSN 1365-8050
|
RSS
|
Atom
Episciences
Documentation
|
Acknowledgements
|
Publishing policy
Accessibility: non-compliant
|
Legal mentions
|
Privacy statement
|
Terms of use
  1. Home > Articles & Issues >
  2. Articles >
  3. Cover time of a rand ...
Conference paper

Cover time of a random graph with given degree sequence

Mohammed Abdullah (1), Colin Cooper (1), Alan Frieze ORCID (2)
(1) Department of Computer Science
(2) Department of Mathematical Sciences [Pittsburgh]
Download article
Open on HAL
Imported on
January 31, 2017
Published on
December 31, 2009
Last modified on
March 31, 2025
Volume
DMTCS Proceedings vol. AM, 21st International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA'10)
Proceedings
DOI
10.46298/dmtcs.2804
License
https://about.hal.science/hal-authorisation-v1
National Science Foundation
0502793
Probabilistic Considerations in the Analysis of Algorithms
Indicators
706
Views
1789
Downloads

Cover time of a random graph with given degree sequence

Mohammed Abdullah (1), Colin Cooper (1), Alan Frieze ORCID (2)
(1) Department of Computer Science
(2) Department of Mathematical Sciences [Pittsburgh]
Abstract
In this paper we establish the cover time of a random graph $G(\textbf{d})$ chosen uniformly at random from the set of graphs with vertex set $[n]$ and degree sequence $\textbf{d}$. We show that under certain restrictions on $\textbf{d}$, the cover time of $G(\textbf{d})$ is with high probability asymptotic to $\frac{d-1}{ d-2} \frac{\theta}{ d}n \log n$. Here $\theta$ is the average degree and $d$ is the $\textit{effective minimum degree}$. The effective minimum degree is the first entry in the sorted degree sequence which occurs order $n$ times.
Keywords
  • [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS]
  • [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO]
  • [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM]
  • [INFO.INFO-CG]Computer Science [cs]/Computational Geometry [cs.CG]
  • Random walks
  • random graphs
  • cover time
Cited by

Source: OpenCitations

  • Learning structure of power-law Markov networks

    2014 IEEE International Symposium on Information Theory

    Authors : Abhik Kumar Das ORCID, Praneeth Netrapalli ORCID, Sujay Sanghavi, Sriram Vishwanath ORCID

    Journal reference : Volume 38, 2014, pp. 2272-2276

    DOI : 10.1109/isit.2014.6875238
  • Analytical results for the distribution of cover times of random walks on random regular graphs

    arXiv (Cornell University)

    Authors : Ido Tishby ORCID, Ofer Biham ORCID, Eytan Katzav ORCID

    Journal reference : Volume 55, 2021, pp. 015003

    DOI : 10.1088/1751-8121/ac3a34
  • A probabilistic proof of Cooper and Frieze's First Visit Time Lemma

    arXiv (Cornell University)

    Authors : Francesco Manzo, Matteo Quattropani ORCID, Elisabetta Scoppola ORCID

    Journal reference : Volume 18, 2021, pp. 1739

    DOI : 10.30757/alea.v18-64
  • Recent results of quantum ergodicity on graphs and further investigation

    Annales de la faculté des sciences de Toulouse Mathématiques

    Authors : Nalini Anantharaman ORCID, Mostafa Sabri ORCID

    Journal reference : Volume 28, 2019, pp. 559-592

    DOI : 10.5802/afst.1609
  • Viral processes by random walks on random regular graphs

    The Annals of Applied Probability

    Authors : Mohammed Abdullah, Colin Cooper ORCID, Moez Draief

    Journal reference : Volume 25, 2015, pp.

    DOI : 10.1214/13-aap1000
  • Stationary distribution and cover time of sparse directed configuration models

    Probability Theory and Related Fields

    Authors : Pietro Caputo ORCID, Matteo Quattropani ORCID

    Journal reference : Volume 178, 2020, pp. 1011-1066

    DOI : 10.1007/s00440-020-00995-6
  • Cutoff for random walk on dynamical Erdős–Rényi graph

    arXiv (Cornell University)

    Authors : Perla Sousi, Sam Thomas

    Journal reference : Volume 56, 2020, pp.

    DOI : 10.1214/20-aihp1057
  • Potential induced random teleportation on finite graphs

    Computational Optimization and Applications

    Authors : Shui-Nee Chow, Xiaojing Ye ORCID, Haomin Zhou ORCID

    Journal reference : Volume 61, 2015, pp. 689-711

    DOI : 10.1007/s10589-015-9727-7
  • Global majority consensus by local majority polling on graphs of a given degree sequence

    Discrete Applied Mathematics

    Authors : Mohammed Amin Abdullah, Moez Draief

    Journal reference : Volume 180, 2014, pp. 1-10

    DOI : 10.1016/j.dam.2014.07.026
  • Discursive Voter Models on the Supercritical Scale-Free Network

    SIAM Journal on Discrete Mathematics

    Authors : John Fernley ORCID

    Journal reference : Volume 38, 2024, pp. 1285-1314

    DOI : 10.1137/22m1544373
  • Cutoff for nonbacktracking random walks on sparse random graphs

    The Annals of Probability

    Authors : Anna Ben-Hamou ORCID, Justin Salez ORCID

    Journal reference : Volume 45, 2017, pp.

    DOI : 10.1214/16-aop1100
  • Voter models on subcritical scale‐free random graphs

    Random Structures and Algorithms

    Authors : John Fernley ORCID, Marcel Ortgiese ORCID

    Journal reference : Volume 62, 2022, pp. 376-429

    DOI : 10.1002/rsa.21107
  • Cover time of a random graph with a degree sequence II: Allowing vertices of degree two

    Random Structures and Algorithms

    Authors : Colin Cooper ORCID, Alan Frieze ORCID, Eyal Lubetzky ORCID

    Journal reference : Volume 45, 2014, pp. 627-674

    DOI : 10.1002/rsa.20573
  • Speeding Up Cover Time of Sparse Graphs Using Local Knowledge

    Lecture notes in computer science

    Authors : Mohammed Amin Abdullah, Colin Cooper ORCID, Moez Draief

    Journal reference : Volume , 2016, pp. 1-12

    DOI : 10.1007/978-3-319-29516-9_1
  • Mixing times of random walks on dynamic configuration models

    The Annals of Applied Probability

    Authors : Luca Avena ORCID, Hakan Güldaş, Remco van der Hofstad ORCID, Frank den Hollander ORCID

    Journal reference : Volume 28, 2018, pp.

    DOI : 10.1214/17-aap1289
Preview
Loading PDF preview...