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

DOI10.1142/S012905412050029XzbMATH Open1461.05186arXiv1805.05387OpenAlexW3081491952MaRDI QIDQ5859639FDOQ5859639

Ameneh Farhadian

Publication date: 19 April 2021

Published in: International Journal of Foundations of Computer Science (Search for Journal in Brave)

Abstract: The paper shows that almost every $n$-vertex graph is such that the multiset of its induced subgraphs on $3lo{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 $3lo{g}_{2}n$-vertex subgraphs is sufficient .

Full work available at URL: https://arxiv.org/abs/1805.05387

Recommendations

• scientific article; zbMATH DE number 1882352
• Ramsey graphs contain many distinct induced subgraphs
• On the number of distinct induced subgraphs of a graph
• scientific article
• Almost universal graphs

zbMATH Keywords

random graphgraph isomorphismgraph reconstructionunique subgraphgraph asymmetry

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Cites Work

• Title not available (Why is that?)
• On a new class of codes for identifying vertices in graphs
• A congruence theorem for trees
• The d-Identifying Codes Problem for Vertex Identification in Graphs: Probabilistic Analysis and an Approximation Algorithm
• Title not available (Why is that?)
• Codes identifying sets of vertices in random networks
• Title not available (Why is that?)

Cited In (3)

• Title not available (Why is that?)
• On the number of unique subgraphs of a graph
• Nonrepetitively 3-colorable subdivisions of graphs with a logarithmic number of subdivisions per edge

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5859639)