- Tytuł:
- The Edit Distance Function of Some Graphs
- Autorzy:
-
Hu, Yumei
Shi, Yongtang
Wei, Yarong - Powiązania:
- https://bibliotekanauki.pl/articles/31518790.pdf
- Data publikacji:
- 2020-08-01
- Wydawca:
- Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
- Tematy:
-
edit distance
colored regularity graphs
hereditary property
clique spectrum - Opis:
- The edit distance function of a hereditary property $ℋ$ is the asymptotically largest edit distance between a graph of density $p ∈ [0, 1]$ and $ℋ$. 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, . . ., v_{n−1}}$ and \(E(\widetilde{C_n})=E(C_n)∪{v_0v_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.
- Źródło:
-
Discussiones Mathematicae Graph Theory; 2020, 40, 3; 807-821
2083-5892 - Pojawia się w:
- Discussiones Mathematicae Graph Theory
- Dostawca treści:
- Biblioteka Nauki
Artykuł