Reconstructing graphs from size and degree properties of their induced \(k\)-subgraphs (Q868330)

The following variant of the graph reconstruction problem is considered: given the information that all induced subgraphs on \(k\) vertices of an unknown graph \(G\) on \(n \geq k\) vertices satisfy a certain property, can we determine the graph \(G\)? In this paper complete solutions are given for all possible values of \(k\) and \(n\) and the following properties: \((P_{a})\) All induced \(k\)-subgraphs are regular (not necessarily of the same degree). \((P_{b})\) All induced \(k\)-subgraphs are regular modulo \(m\) (not necessarily of the same residual degree). \((P_{c})\) All induced \(k\)-subgraphs have one of two possible numbers of edges. Complete solutions for every \(k\) and sufficiently large \(n\) are given for: \((P_{d})\) All induced \(k\)-subgraphs are biregular. \((P_{e})\) All induced \(k\)-subgraphs have a bounded difference between the maximum and the minimum degree.