Almost every n-vertex graph is determined by its 3 _2n-vertex subgraphs

Abstract: The paper shows that almost every

n

-vertex graph is such that the multiset of its induced subgraphs on

3 l o g_{2} n

vertices is sufficient to determine it up to isomorphism. Therefore, for checking the isomorphism of a pair of

n

-vertex graphs, almost surely the multiset of their

3 l o g_{2} n

-vertex subgraphs is sufficient .

Recommendations

Cites work

Cited in

(3)

This page was built for publication: Almost every \(n\)-vertex graph is determined by its \(3 \log_2n\)-vertex subgraphs