Some Indices of Alphabet Overlap Graph

The undirected de Bruijn graph is often used as the model of communication network for its useful properties, such as short diameter, small maximum vertex degree. In this paper, we consider the alphabet overlap graph G(k, d, s): the vertex set V=v|v=(v₁...v_k); v_i∈1, 2,..., d, i=1, 2,..., k; they are distinct and two vertices u=(u₁... u_k) and v=(v₁... v_k) are adjacent if and only if u_s+i=v_i or v_s+i=u_i (i=1, 2,..., k-s). In particular, when s=1, G(k, d, s) is just an undirected de Bruijn graph. First, we give a formula to calculate the vertex degree of G(k, d, s). Then, we use the corollary of Menger’s theorem to prove that the connectivity of G(k, d, s) is 2d^s-2d^2s-k for s ≥ k/2.