Volume 16, No 4, 2009, P. 87-96

UDC 519.1
P. V. Skums, R. I. Tyshkevich
Reconstruction conjecture for graphs with restrictions for 4-vertex paths

Abstract:
The well-known Kelly–Ulam reconstruction conjecture is considered. It is proved that the conjecture holds for $P_4$-disconnected and $P_4$-tidy graphs. In particular, it generalizes the known results on the reconstructibility of disconnected graphs, complements of disconnected graphs, 1-decomposable graphs, and $P_4$-reducible graphs.
Bibl. 19.

Keywords: reconstruction conjecture, $P_4$-disconnected graphs, $P_4$-tidy graphs, $P_4$-reducible graphs, 1-decomposable graphs.

Skums Pavel Valentinovich ¹
Tyshkevich Regina Iosiphovna ¹
1. Belarusian State University,
4 Nezavisimosti ave., 220030 Minsk, Belarus
e-mail: skumsp@gmail.com, tyshkevich@bsu.by