论文标题
修改图的度序列和度序列属性的测试
Modifying a Graph's Degree Sequence and the Testablity of Degree Sequence Properties
论文作者
论文摘要
我们表明，如果图$ g $的度序列在$ \ ell_1 $ distance中与给定的可靠度序列$（d_1，\ dots，d_n）$接近，则$ g $在编辑距离上与semence $（d_1，\ dots，d_n）$的编辑距离接近。然后，我们使用此结果来证明，根据度序列定义的每个图形属性都可以在密集的图模型中测试，其查询复杂性与$ n $无关。
We show that if the degree sequence of a graph $G$ is close in $\ell_1$-distance to a given realizable degree sequence $(d_1,\dots,d_n)$, then $G$ is close in edit distance to a graph with degree sequence $(d_1,\dots,d_n)$. We then use this result to prove that every graph property defined in terms of the degree sequence is testable in the dense graph model with query complexity independent of $n$.
