Random subgraphs of certain graph powers

1. Introduction. A finite, simple, undirected graph G has vertex set V( G)and edge set E(G). The order of G is | V( G)| and the size e(G) of G is |E(G)| .F orS ⊆ V( G) ,l et G[S] denote the subgraph of G induced by S and G[S,V (G)−S] denote the spanning subgraph of G with edges xy where x ∈ S and y ∈ V( G)− S .F orU ⊆ V( G) ,l et NG(U) ={ y ∈ V( G): ∃xy ∈ E(G) with x ∈ U} and NG(U) = NG(U) ∪ U. Of course, NG(v) = NG({v}) and the degree dG(v) of v in G is |NG(v)| for v ∈ V( G) .F orS ⊆ V( G) ,l etbG(S) =| {xy ∈ E(G) : x ∈ S, y ∈ V( G)− S}| and bG(s) = min{bG(S) : S ⊆ V( G), |S |= s} (0 ≤ s ≤| V( G)|).