Dense graphs and edge reconstructions

DOI10.1007/BF01271270MaRDI QIDQ1375698zbMATH OpenFDO

Authors Laszló Pyber

Publication date 11 January 1998

Published in Combinatorica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/BF01271270

zbMATH Keywords

dense graphsedge reconstructionset systems

Mathematics Subject Classification ID

Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Review text

Nash-Williams proved that if a graph \(G\) is not edge reconstructible, then for all \(A \subset E(G)\), \(|A|\equiv |E(G)|\pmod {2}\) there is a permutation \(\phi\) of \(V(G)\) such that \(E(G) \cap E(G\phi)=A\). The author shows that the previous result cannot settle the edge reconstruction conjecture by exhibiting an arbitrarily large graph which satisfies the Nash-Williams condition but still \(e \geq n \lfloor \sqrt{1/2 \log n} \rfloor\), where \(e\) and \(n\) stand for the number of edges and vertices, respectively.

Recommendations

• scientific article; zbMATH DE number 4077273
• scientific article; zbMATH DE number 4162922
• Some applications of the Nash-Williams lemma to the edge-reconstruction conjecture
• On the Nash-Williams' lemma in graph reconstruction theory
• Some results and approaches for reconstruction conjectures

Cites work

• A note on the edge-reconstruction of \(K_{1,m}\)-free graphs
• A note on the line reconstruction problem
• Claw‐free graphs are edge reconstructible
• scientific article; zbMATH DE number 17789 (Why is no real title available?)
• scientific article; zbMATH DE number 68355 (Why is no real title available?)
• The edge reconstruction of hamiltonian graphs

Cited in

(7)

• Some results and approaches for reconstruction conjectures
• On the Nash-Williams' lemma in graph reconstruction theory
• The edge reconstruction of hamiltonian graphs
• scientific article; zbMATH DE number 4162922 (Why is no real title available?)
• scientific article; zbMATH DE number 4077273 (Why is no real title available?)
• scientific article; zbMATH DE number 7029306 (Why is no real title available?)
• Some applications of the Nash-Williams lemma to the edge-reconstruction conjecture

This page was built for publication: Dense graphs and edge reconstructions

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