Reconstruction Number of Separable Self-Complementary Graphs and Others

Abstract

We prove that each graph in two infinite families is fixed uniquely by just two of its maximal induced subgraphs, with each of which the degree of the missing vertex is also given. One of these families contains all separable self-complementary graphs and a self-complementary graph of diameter \(3\) and order \(n\) for each \(n \geq 5\) such that \(n \equiv 0\) or \(1 \pmod{4}\). The other contains a Hamiltonian self-complementary graph of diameter \(2\) and order \(n\) for each admissible \(n \geq 8\).