Almost Every n-Vertex Graph is Determined by Its 3log2n-Vertex Subgraphs

DOI10.1142/S012905412050029XzbMath1461.05186arXiv1805.05387OpenAlexW3081491952MaRDI QIDQ5859639

Ameneh Farhadian

Publication date: 19 April 2021

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

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

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

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A congruence theorem for trees
• Codes identifying sets of vertices in random networks
• The d-Identifying Codes Problem for Vertex Identification in Graphs: Probabilistic Analysis and an Approximation Algorithm
• On a new class of codes for identifying vertices in graphs

This page was built for publication: Almost Every n-Vertex Graph is Determined by Its 3log2n-Vertex Subgraphs