The edit distance function of some graphs

DOI10.7151/DMGT.2154MaRDI QIDQ2175239zbMATHOpenAlexWikidataFDO

Authors Yumei Hu, Yongtang Shi, Yarong Wei

Publication date 28 April 2020

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

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

zbMATH Keywords

edit distancehereditary propertycolored regularity graphsclique spectrum

Mathematics Subject Classification ID

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

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}^{\ast }$ 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^{\ast }$. 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^{\ast }$, $widetilde{C}_n$ and $P_n$, respectively.

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

Cites work

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

Cited in

(5)

• Edit distance measure for graphs.
• ON THE EDITING DISTANCE BETWEEN UNDIRECTED ACYCLIC GRAPHS
• The edit distance function and symmetrization
• On the edit distance function of the random graph
• 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)