Modifying a Graph's Degree Sequence and the Testablity of Degree Sequence Properties

2020/09/26 by Gishboliner, Lior
#Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics

paper · doi:10.48550/arxiv.2009.12697

Abstract

We show that if the degree sequence of a graph G is close in ℓ₁-distance to a given realizable degree sequence (d₁,…,d_n), then G is close in edit distance to a graph with degree sequence (d₁,…,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.

Related

• Testing versus estimation of graph properties, revisited
• On Testability of First-Order Properties in Bounded-Degree Graphs
• NP-Hardness and Fixed-Parameter Tractability of Realizing Degree Sequences with Directed Acyclic Graphs
• Graph Realizations: Maximum and Minimum Degree in Vertex Neighborhoods
• On Testability of First-Order Properties in Bounded-Degree Graphs and Connections to Proximity-Oblivious Testing