Some Indices of Alphabet Overlap Graph |
| |
Authors: | Rong Yang Zhao-Lan Yang He-Ping Zhang |
| |
Affiliation: | 1 School of Mathematics and Statistics,Lanzhou University,Lanzhou 730000,China 2 Normal School,Gansu Lianhe University,Lanzhou 730000,China |
| |
Abstract: | 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 = (v1 ...vk);vi ∈ {1,2,...,d},i = 1,2,...,k};they are distinct and two vertices u = (u1 ...uk) and v = (v1 ...vk) are adjacent if and only if us+i = vi or vs+i = ui (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 2ds 2d2s k for s k/2. |
| |
Keywords: | undirected de Bruijn graph alphabet overlap graph vertex degree connectivity |
本文献已被 CNKI SpringerLink 等数据库收录! |
|