Deviation estimates for Eulerian edit numbers of random graphs

DOI10.1016/J.SPL.2020.109025zbMATH Open1460.05172arXiv2103.00770OpenAlexW3116702030MaRDI QIDQ2658005FDOQ2658005

Authors: Ghurumuruhan Ganesan 

Publication date: 18 March 2021

Published in: Statistics \& Probability Letters (Search for Journal in Brave)

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~(frac{n}{4}) operations suffice in all three cases.

Full work available at URL: https://arxiv.org/abs/2103.00770

Recommendations

• Editing to Eulerian graphs
• scientific article; zbMATH DE number 4110728
• On the edit distance function of the random graph
• Editing to Eulerian graphs
• Edit distance measure for graphs.

zbMATH Keywords

random graphsdeviation estimatesEulerian edit numbers

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10)

Cites Work

• The probabilistic method. With an appendix on the life and work of Paul Erdős.
• The spanning subgraphs of eulerian graphs
• The maximum edit distance from hereditary graph properties
• The edit distance in graphs: Methods, results, and generalizations
• Phase transition in inhomogenous Erdős-Rényi random graphs via tree counting

This page was built for publication: Deviation estimates for Eulerian edit numbers of random graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2658005)