Removing induced powers of cycles from a graph via fewest edits
Preprint
Abstract
What is the minimum proportion of edges which must be added to or removed from a graph of density $p$ to eliminate all induced cycles of length $h$? The maximum of this quantity over all graphs of density $p$ is measured by the edit distance function, $\text{ed}_{\text{Forb}(C_h)}(p)$, a function which provides a natural metric between graphs and hereditary properties. Martin determined $\text{ed}_{\text{Forb}(C_h)}(p)$ for all $p \in [0,1]$ when $h \in \{3, \ldots, 9\}$ and determined $\text{ed}_{\text{Forb}(C_{10})}(p)$ for $p \in [1/7, 1]$. Peck determined $\text{ed}_{\text{Forb}(C_h)}(p)$ for all $p \in [0,1]$ for odd cycles, and for $p \in [ 1/\lceil h/3 \rceil, 1]$ for even cycles. In this paper, we fully determine the edit distance function for $C_{10}$ and $C_{12}$. Furthermore, we improve on the result of Peck for even cycles, by determining $\text{ed}_{\text{Forb}(C_h)}(p)$ for all $p \in [p_0, 1/\lceil h/3 \rceil ]$, where $p_0 \leq c/h^2$ for a constant $c$. More generally, if $C_h^t$ is the $t$-th power of the cycle $C_h$, we determine $\text{ed}_{\text{Forb}(C_h^t)}(p)$ for all $p \geq p_0$ in the case when $(t+1) \mid h$, thus improving on earlier work of Berikkyzy, Martin and Peck.
Keywords
All Related Versions
This publication has 7 references indexed in Scilit:
- On the edit distance function of the random graphCombinatorics, Probability and Computing, 2021
- On the edit distance of powers of cyclesDiscrete Mathematics, 2019
- On the Edit Distance from K2,t-Free GraphsJournal of Graph Theory, 2013
- The Edit Distance Function and SymmetrizationThe Electronic Journal of Combinatorics, 2013
- Multicolor and directed edit distanceJournal of Combinatorics, 2011
- What is the furthest graph from a hereditary property?Random Structures & Algorithms, 2008
- A distance measure between attributed relational graphs for pattern recognitionIEEE Transactions on Systems, Man, and Cybernetics, 1983