The reconstruction conjecture is true if all 2-connected graphs are reconstructible
✍ Scribed by Yang Yongzhi
- Publisher
- John Wiley and Sons
- Year
- 1988
- Tongue
- English
- Weight
- 344 KB
- Volume
- 12
- Category
- Article
- ISSN
- 0364-9024
No coin nor oath required. For personal study only.
✦ Synopsis
It is shown that the Reconstruction Conjecture is true for all finite graphs if it is true for the 2-connected ones.
We shall, for the most part, use the terminology of [2] and [ 4 ] . Graphs will be finite, simple, and undirected. Let G be a graph and u E V(G). Denote by d(u) the degree of u in G and by c, the complement of G. A pendant edge is an edge joined to an endvertex. The degree-sequence of u in G [denoted by VS, ( u ) or VS(u)] is the sequence obtained by listing the degrees of the neighbors of u in nondecreasing order. Bridges and maximal 2-connected subgraphs of G are called blocks of G , and a vertex with the property that its deletion disconnects G is called a cutvertex of G. Let H be a graph.
We say that H and G are hypomorphic if there exists a hypomorphism of G onto H. A graph G is reconstructible if every graph hypomorphic to G is isomorphic to G [ 4 ] . (Alternatively, we say that a graph G is reconstructible if G is uniquely determined by {G -u}, the collection of all the vertex-deleted subgraphs of G). If a property P of G is uniquely determined by {G -u}, we say that P is recognizable. The Reconstruction Conjecture is that all finite graphs on at least three vertices are reconstructible. It is known that all graphs with less than ten vertices as well as disconnected graphs are reconstructible (see 121). So we hereafter assume G, H , and f are as above, and that G and H are connected with at least ten vertices.