Some Indices Of Alphabet Overlap Graphs

The undirected de Bruijn graphs are often used as models of communication network for their useful properties, such as short diameter, small maximum vertex degree and plenty of vertices. We consider a class of graphs more general than the undirected de Bruijn graphs called alphabet overlap graphs G(k, d, s). These graphs have the vertex set V = {v|v = (v₁, ... ,v_k); v_i∈{1,2, ...,d}(1≤i≤k)}, two distinct vertices u = (u₁,...,u_k) and v = (v₁,...,v_k) are adjacent if and only if u_i+s = v_i (1≤i≤k-s) or v_i+s = u_i (1≤i≤k - s). Hence, when s = 1, alphabet overlap graphs are just undirected de Bruijn graphs. In this paper, we obtain some results of alphabet overlap graphs G(k, d, s): the formula for the the vertex degree of G(k, d, s), the diameter and the grith of G(k, d, s) which are [k/s] and 3 respectively, d^s + 1 of its automorphisms. For s≥k/2, we prove that the connectivity of G(k, d, s) is 2d^s - 2d^k-2t as well as G(k, d, s) is super edge connected.