The edit distance function of some graphs

DOI10.7151/DMGT.2154zbMATH Open1439.05116arXiv1707.07170OpenAlexW2963359962WikidataQ129228409 ScholiaQ129228409MaRDI QIDQ2175239FDOQ2175239

Authors: Yumei Hu, Yongtang Shi, Yarong Wei 

Publication date: 28 April 2020

Published in: Discussiones Mathematicae Graph Theory (Search for Journal in Brave)

Abstract: The edit distance function of a hereditary property $mathscrH$ is the asymptotically largest edit distance between a graph of density $pin[0,1]$ and $mathscrH$. Denote by $P_n$ and $C_n$ the path graph of order $n$ and the cycle graph of order $n$, respectively. Let $C_{2n}^{*}$ be the cycle graph $C_{2n}$ with a diagonal, and $widetilde{C}_n$ be the graph with vertex set $v_0,v_1,ldots,v_{n-1}$ and $E(widetilde{C}_n)=E(C_n)cup{v}_0{v}_2$. Marchant and Thomason determined the edit distance function of $C_6^{*}$. Peck studied the edit distance function of $C_n$, while Berikkyzy et al. studied the edit distance of powers of cycles. In this paper, by using the methods of Peck and Martin, we determine the edit distance function of $C_8^{*}$, $widetilde{C}_n$ and $P_n$, respectively.

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

Recommendations

• On the edit distance of powers of cycles
• The edit distance function and symmetrization
• On the computation of edit distance functions
• The edit distance in graphs: methods, results, and generalizations
• On the edit distance function of the random graph

zbMATH Keywords

edit distancehereditary propertycolored regularity graphsclique spectrum

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Coloring of graphs and hypergraphs (05C15)

Cites Work

• Graph theory
• Efficient testing of large graphs
• Edit distance and its computation
• On the computation of edit distance functions
• Testing subgraphs in large graphs
• Extremal graphs and multigraphs with two weighted colours
• On the editing distance of graphs
• What is the furthest graph from a hereditary property?
• The edit distance function and symmetrization
• The Algorithmic Aspects of the Regularity Lemma
• On the edit distance from \(K_{2,t}\)-free graphs
• The edit distance in graphs: Methods, results, and generalizations
• Title not available (Why is that?)
• On the edit distance of powers of cycles

Cited In (3)

• On the edit distance function of the random graph
• ON THE EDITING DISTANCE BETWEEN UNDIRECTED ACYCLIC GRAPHS
• On the edit distance of powers of cycles

This page was built for publication: The edit distance function of some graphs

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