Reconstructing graphs from size and degree properties of their induced k-subgraphs

AbstractAs a variant of the famous graph reconstruction problem we characterize classes of graphs of order n such that all their induced subgraphs on k⩽n vertices satisfy some property related to the number of edges or to the vertex degrees.We give complete solutions for the properties (i) to be regular, (ii) to be regular modulo m⩾2 or (iii) to have one of two possible numbers of edges. Furthermore, for an order n large enough, we give solutions for the properties (iv) to be bi-regular or (v) to have a bounded difference between the maximum and the minimum degree