Deviation estimates for Eulerian edit numbers of random graphs

Ghurumuruhan Ganesan

Statistics & Probability Letters, 2021, vol. 171, issue C

Abstract: Consider the random graph G(n,p) obtained by allowing each edge in the complete graph on n vertices to be present with probability p independent of the other edges. In this paper, we study the minimum number of edge edit operations needed to convert G(n,p) into an Eulerian graph. We obtain deviation estimates for three types Eulerian edit numbers based on whether we perform only edge additions or only edge deletions or a combination of both and show that with high probability, roughly n4 operations suffice in all three cases.

Keywords: Eulerian edit numbers; Random graphs; Deviation estimates (search for similar items in EconPapers)
Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S016771522030328X
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:stapro:v:171:y:2021:i:c:s016771522030328x

Ordering information: This journal article can be ordered from
http://www.elsevier.com/wps/find/supportfaq.cws_home/regional
https://shop.elsevie ... _01_ooc_1&version=01

DOI: 10.1016/j.spl.2020.109025

Access Statistics for this article

Statistics & Probability Letters is currently edited by Somnath Datta and Hira L. Koul

More articles in Statistics & Probability Letters from Elsevier
Bibliographic data for series maintained by Catherine Liu ().