Recognizing generalized sierpiński graphs

Let H be an arbitrary graph with vertex set V (H) = [n_H] = [1, . . . , n_H]. The generalized Sierpiński graph Sⁿ_H , n ∈, is defined on the vertex set [n_H]ⁿ, two different vertices u = u_n . . . u₁ and v = v_n . . . v₁ being adjacent if there exists an h ∈ [n] such that (a) u_t = v_t, for t > h, (b) u_h ≠ v_h and u_hv_h ∈ E(H), and (c) u_t = v_h and v_t = u_h for t < h. If H is the complete graph K_k, then we speak of the Sierpiński graph Sⁿ_k. We present an algorithm that recognizes Sierpiński graphs Sⁿ_k in O(|V (Sⁿ_k)|1+1/ⁿ) = O(|E(Sⁿ_k)|) time. For generalized Sierpiński graphs Sⁿ_H we present a polynomial time algorithm for the case when H belong to a certain well defined class of graphs. We also describe how to derive the base graph H from an arbitrarily given Sⁿ_H.