On the edit distance from \(K_{2,t}\)-free graphs
type: Item
instance of: scholarly article
zbMATH Open document ID: 1302.05045
author: Ryan R. Martin
author: Tracy McKay
published in: Journal of Graph Theory
publication date: 2014-10-09T00:00:00Z
full work available at URL: https://arxiv.org/abs/1012.0800
Mathematics Subject Classification ID: 05C12
Mathematics Subject Classification ID: 05C35
Mathematics Subject Classification ID: 05C80
Mathematics Subject Classification ID: 05E30
Mathematics Subject Classification ID: 90C20
zbMATH DE Number: 6353348
zbMATH Keywords: edit distance
zbMATH Keywords: quadratic programing
zbMATH Keywords: strongly regular graphs
MaRDI profile type: Publication
OpenAlex ID: W1831593326
arXiv ID: 1012.0800
cites work: What is the furthest graph from a hereditary property?
cites work: On the editing distance of graphs
cites work: Edit distance and its computation
cites work: On the Structure of Dense Triangle-Free Graphs
cites work: On Graphs that do not Contain a Thomsen Graph
cites work: Saturation numbers of books
cites work: Values of lambda and mu for which there are only finitely many feasible (v,k,lambda,mu)
cites work: New asymptotics for bipartite Turán numbers
cites work: The edit distance function and symmetrization
cites work: Boundedness of optimal matrices in extremal multigraph and digraph problems
DOI: 10.1002/JGT.21777
title: On the edit distance from \(K_{2,t}\)-free graphs
review text: Let \(\operatorname{Forb}(H)\) be the hereditary property that consists of the graphs with no induced copy of a single graph \(H\). In this paper, the entire edit distance functions for \(\operatorname{Forb}(K_{2,3})\) and \(\operatorname{Forb}(K_{2,4})\) are computed. Some upper bounds for the edit distance function of \(\operatorname{Forb}(K_{2,t})\) are derived.
reviewed by: Hang Lau
description: scientific article; zbMATH DE number 6353348