Disproof of a conjecture in graph reconstruction theory (Q1200285)

From MaRDI portal





scientific article; zbMATH DE number 96969
Language Label Description Also known as
English
Disproof of a conjecture in graph reconstruction theory
scientific article; zbMATH DE number 96969

    Statements

    Disproof of a conjecture in graph reconstruction theory (English)
    0 references
    17 January 1993
    0 references
    In his thesis B. D. Thatte (1990) conjectured that any finite sequence of finite connected graphs with the same number of vertices and edges can be uniquely reconstructed from its shuffled edge deck. The author shows that the conjecture is false. A small mistake is found on p. 367. In the sequence \({\mathcal G}_ 1=G_ 1,G_ 2,G_ 2,G_ 2,G_ 2\) the nontrivial component of \(G_ 1\) ought to be a star on five vertices.
    0 references
    0 references
    graph reconstruction
    0 references
    shuffled edge deck
    0 references
    conjecture
    0 references
    0 references

    Identifiers