Random interdependent networks consist of a group of subnetworks where each edge between two different subnetworks is formed independently with probability p. In this paper, we investigate certain spectral and structural properties of such networks, with corresponding implications for certain variants of consensus and diffusion dynamics on those networks. We start by providing a characterization of the isoperimetric constant in terms, of the inter-network edge formation probability p. We then analyze the algebraic connectivity of such networks, and provide an asymptotically tight rate of growth of this quantity for a certain range of inter-network edge formation probabilities. Next, we give bounds on the smallest eigenvalue of the grounded Laplacian matrix (obtained by removing certain rows and columns of the Laplacian matrix) of random interdependent networks for the case where the removed rows and columns correspond to one of the subnetworks. Finally, we study a property known as r-robustness, which is a strong indicator of the ability of a network to tolerate structural perturbations and dynamical attacks. Our results yield new insights into the structure and robustness properties of random interdependent networks. (C) 2017 Elsevier Ltd. All rights reserved.