Reconstruction of graphs with certain degree-sequences. (English) Zbl 0821.05043

The purpose of this note is to present some results concerning the Kelly- Ulam conjecture for graphs whose degree-sequences satisfy some extra conditions. Throughout, the graphs considered are finite, simple and undirected. A subgraph of a graph \(G\) obtained by deleting a vertex \(v\) together with all edges incident with \(v\) will be referred to as a vertex-deleted subgraph and denoted by \(G- v\). A graph \(G^*\) will be called a reconstruction of a graph \(G\) if there is bijection \(f: V(G)\to V(G^*)\) such that \(G- u\) is isomorphic to \(G^*- f(u)\) for all \(u\in V(G)\). A graph \(G\) will be called reconstructible if each of its reconstructions is isomorphic to \(G\). The famous Kelly-Ulam reconstruction conjecture states that any graph with more than two vertices is reconstructible. The conjecture is apparently very hard, and only a few classes of reconstructible graphs are known.
It is easily seen that regular graphs are reconstructible. Going a step further, J. A. Bondy and R. L. Hemminger [J. Graph Theory 1, 227-268 (1977; Zbl 0375.05040)] define a vertex \(v\) of \(G\) to be bad if \(G\) has some vertex of degree \(d(v)- 1\), and remark that a graph with at least 3 vertices is reconstructible whenever it contains a vertex with no bad neighbours. This result was extended by J. Širáň [Math. Slovaca 32, 403-404 (1982; Zbl 0502.05045)] proving that a graph \(G\) with more than two vertices is reconstructible provided that \(G\) contains a vertex \(v\) such that for any of its neighbours \(w\) all vertices of \(G\) of degree \(d(w)- 1\) that are distinct from \(v\) are neighbours of \(v\). It is also obvious that \(G\) is reconstructible if \(\sum_{v\in B} d(v)< n\), where \(B\) is the set of bad vertices of \(G\) and \(n\) is the number of vertices of \(G\). In [C. St. J. A. Nash- Williams, Reconstruction using degree sequences (unpublished)] this observation was extended by proving that \(G\) is reconstructible if \(\sum_{v\in B} (d(v)- 1/2)< n\).
The first part of the paper is devoted to proving results of similar flavour as the results above. In the second part we introduce the concept of reconstruction matrix of graphs and establish a Kelly-Ulam type result for graphs with certain reconstruction matrices.


05C60 Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.)
Full Text: EuDML EMIS