›› 2012,Vol. 27 ›› Issue (4): 897-902.doi: 10.1007/s11390-012-1261-9

• • 上一篇    

字母重叠图的一些指标

Rong Yang1 (杨荣), Zhao-Lan Yang2 (杨兆兰), and He-Ping Zhang1 (张和平)   

  • 收稿日期:2011-08-26 修回日期:2012-03-12 出版日期:2012-07-05 发布日期:2012-07-05

Some Indices of Alphabet Overlap Graph

Rong Yang1 (杨荣), Zhao-Lan Yang2 (杨兆兰), and He-Ping Zhang1 (张和平)   

  1. 1. School of Mathematics and Statistics, Lanzhou University, Lanzhou 730000, China;
    2. Normal School, Gansu Lianhe University, Lanzhou 730000, China
  • Received:2011-08-26 Revised:2012-03-12 Online:2012-07-05 Published:2012-07-05

无向de bruijn 图有很多好的性质,比如较小的直径、 较大的顶点度等, 经常用来做通讯网络的设计。 本文中,我们考虑了字母重叠图G(k, d, s):它的顶点集为V={v|v=(v1...vk);vi∈{1, 2,..., d}, i=1, 2,..., k}。两个不同的顶点u=(u1... uk), v=(v1... vk)相邻,当且仅当us+i=vi或者vs+i=ui (i=1, 2,..., k-s)。特别是当s=1时,G(k, d, s)正好是无向de bruijn 图。 在此文中,首先,我们给出了计算G(k, d, s)的顶点度的公式;其次,我们应用Menger定理证明了当 时, G(k, d, s)的连通度为2ds-2d2s-k

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 sk/2.

[1] Diestel R. Graph Theory (2nd edition), Springer-Verlag, 2000.

[2] Godbole A, Knisley D, Norwood R. Some properties of alphabetoverlap graphs, http://arxiv.org/abs/math/0510094.

[3] Patwardhan R, Tang H, Kim S, Dalkilie M. An approximatede Bruijn graph approach to multiple local alignment and mitif discovery on protein sequences. In Proc. the 1st InternationalConference on Data Mining and Bioinformatics,Sept. 2006, pp.158-169.

[4] Lin H. 1-Fair alternator designs for the de Bruijn network

[Master’s Thesis]. National Sun Yat-sen University, 2006.

[5] Abed S, Mokhtari Y, Ait-Mohamed O, Tahar S. NuMDG: Anew tool for multiway decision graphs construction. Journalof Computer Science and Technology, Jan. 2011, 26(1):139-152.

[6] Debra K, Yared N, Attila P. On the chromatic number of α-overlap graphs. Journal of Combinatorial Mathematics and Computational Computing, 2010, 73: 3-13.

[7] Blasewicz J, Hertz A, Kobler D, de Werra D. On some propertiesof DNA graphs. Discrete Appl. Math., 1999, 98(1/2):1-19.

[8] Wang S, Yuan J. DNA computing of directed line-graphs.Communications Mathematical and in Computer Chemistry,2006, 56(3): 479-484.

[9] Li X Y, Zhang H P. Embedding on alphabet overlap digraphs.J. Math. Chem., 2010, 47(1): 62-71.

[10] Rivals E, Rahmann S. Combinatorics of periods in strings. J.Combin. Theory, Series A, 2003, 104(1): 95-113.

[11] Liu C H, Zhang K M. Super connectivity and restricted connectivityof undirected de Bruijn graph. Acta MathematicaeApplicatae Sinica., 2002, 25(1): 29-35.
No related articles found!
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
[1] 李万学;. Almost Optimal Dynamic 2-3 Trees[J]. , 1986, 1(2): 60 -71 .
[2] 黎仁蔚;. Soundness and Completeness of Kung s Reasoning Procedure[J]. , 1988, 3(1): 7 -15 .
[3] 周巢尘; 柳欣欣;. Denote CSP with Temporal Formulas[J]. , 1990, 5(1): 17 -23 .
[4] 朱明远;. Two Congruent Semantics for Prolog with CUT[J]. , 1990, 5(1): 82 -91 .
[5] 庄南;. Design of Quaternary ECL Q Gate[J]. , 1991, 6(1): 32 -36 .
[6] 张钹; 张铃;. A Relation Matrix Approach to Labelling Temporal Relations in Scheduling[J]. , 1991, 6(4): 339 -346 .
[7] 郑方青;. The Decomposition of Belief Function[J]. , 1992, 7(2): 189 -192 .
[8] 沈一栋;. Form alizing Incomplete Knowledge in Incomplete Databases[J]. , 1992, 7(4): 295 -304 .
[9] 蒋昌俊; 吴哲辉;. Net Operations[J]. , 1992, 7(4): 333 -344 .
[10] 招兆铿; 戴军; 陈文丹;. Automated Theorem Proving in Temporal Logic:T-Resolution[J]. , 1994, 9(1): 53 -62 .
版权所有 © 《计算机科学技术学报》编辑部
本系统由北京玛格泰克科技发展有限公司设计开发 技术支持:support@magtech.com.cn
总访问量: