| A NEW PROPERTY OF BINARY UNDIRECTED de BRUIJN GRAPHS |
| |
| 作者姓名： | XU Junming |
| |
| 作者单位： | [1]DepartmentofMathematics,UniversityofScienceandTechnologyofChina,Hefei230026,China [2]DepartmentofMathematics.NaniingUniversity,Naniing210093,China. [3]ProjectsupportedbytheNationalNaturalScienceFoundationofChina（No.19971086and1987-1040）andtheJiangsuProvincialNaturalScienceFoundationofChina.,Naniing210093,China. |
| |
| 基金项目： | National Natural Science Foundation of China !No. 19971086,19871040，Jiangsu Provincial Natural Science Foundation of China |
| |
| 摘 要： | 1.IntroductionThen-dimensionalbinarydirecteddeBruijngraph,denotedbyB(n),hasthevertex-set{xlxz'xu:xiE{0,1}}.TherearetwoarcsfromavertexxlxZ'xutothevenicesxzxa'x.-lx.0andxZx3'x.-l-c.1.Then-dimensionalbinaryundirecteddeBruijngraph,denotedbyUB(n),isobtainedfromB(n)bydeletingtheorientationofthearcsandthenomittingmultipleedgesandloops.ItiswellknownthatUB(n)hasdiameternandconnectivitytwo.ThedeBruijngraphshavebeenwidelyusedincodingtheory6].Theyhavebeenalsoproposedasapossiblegoodcomputeri…
|
| 关 键 词： | 德布鲁因图 直径 顶点 优势数 |
| 收稿时间： | 17 May 1998 |
| 修稿时间： | 8/6/1999 12:00:00 AM |
A NEW PROPERTY OF BINARY UNDIRECTED de BRUIJN GRAPHS |
| |
| XU Junming.A NEW PROPERTY OF BINARY UNDIRECTED de BRUIJN GRAPHS[J].Chinese Annals of Mathematics,Series B,2000,21(1):39-42. |
| |
| Authors: | XU Junming |
| |
| Institution: | 1. Department of Mathematics, University of Science and Technology of China, Hefei 230026, China
2. Department of Mathematics,Nanjing University,Nanjing 210093,China |
| |
| Abstract: | The authors obtain a new property of then-dimensional binary undirected de Bruijn graphUB(n) forn ≥ 4, namely, there is a vertexx such that for any other vertexy there exist at least two internally disjoint paths of length at mostn- 1 betweenx andy inUB(n). The result means that the (n-1, 2)-dominating number ofUB(n) is equal to one ifn ≥ 4.
Project supported by the National Natural Science Foundation of China (No. 19971086 and 1987-1040) and the Jiangsu Provincial
Natural Science Foundation of China. |
| |
| Keywords: | de Bruijn graph Wide-diameter Length of path Dominating number |
| 本文献已被 CNKI 维普 万方数据 SpringerLink 等数据库收录！ |
| 点击此处可从《数学年刊B辑(英文版)》浏览原始摘要信息 |
| 点击此处可从《数学年刊B辑(英文版)》下载免费的PDF全文 |
