We analyze the diameter and mean internode distance of recursive circulant graphs G($2^m$,4) proposed recently in [PC91] when some nodes or edges fail. Under one node or edge failure, the diameter of G($2^m$,4), m≥4, remains nonincreasing, and the increment of mean internode distance of G($2^m$, 4) is negligible. The fault diameter of G($2^m$, 4) m≥5, is less than or equal to m, which is comparable with fault diameter m+1 of a hypercube $Q_m$ with the same number of nodes and edges as G($2^m$, 4).
Embedding from meshes to recursive circulant graphs G($2^m$, 4) is also considered, $2^{n_1}×2^{n_2}$ mesh and $2^{n_1}×2^{n_2}×2^{2n_3}$ mesh are shown to be a subgraph of G($2^{n_1+n_2}$,4) and G($2^{n_1+n_2+2n_3}$, 4), respectively. Furthermore, we prove that $2^{n_1}×2^{n_2}$ mesh and $2^{n_1}×2^{n_2}×2^{2n_3}$ mesh with wrap-around edges can be embedded to G($2^m$, 4) with dilation two.
