A new digraphs composition with applications to de Bruijn and generalized de Bruijn digraphs

被引：6
|
作者：
Barth, D
Heydemann, MC
机构：
[1] LRI, UA 410 CNRS, Université de Paris-Sud
来源：
DISCRETE APPLIED MATHEMATICS | 1997年 / 77卷 / 02期
关键词：
digraph; DeBruijn digraph; Kautz digraph; kappa-factor;
D O I：
10.1016/S0166-218X(96)00130-8
中图分类号：
O29 [应用数学];
学科分类号：
070104 ;
摘要：
In this paper, we introduce a new operation on digraphs that we apply to different cases; we give new results about deBruijn digraphs and generalized deBruijn digraphs. We prove that this new operation commutes with the operation of taking the line digraph. In particular, we give a simple construction of the Kautz digraph of diameter n from two de Bruijn digraphs of diameter n - 1 and n. We also study kappa-factors in the composed digraph with application to the counting of 1-factors of deBruijn and Kautz digraphs.
引用
收藏
页码：99 / 118
页数：20
相关论文
共 50 条
  • [1] A new digraphs composition with applications to de Bruijn and generalized de Bruijn digraphs (vol 77, pg 99, 1997)
    Barth, D
    Heydemann, MC
    DISCRETE APPLIED MATHEMATICS, 1997, 80 (01) : 115 - 115
  • [2] GENERALIZED DE BRUIJN DIGRAPHS
    DU, DZ
    HWANG, FK
    NETWORKS, 1988, 18 (01) : 27 - 38
  • [3] Absorbant of generalized de Bruijn digraphs
    Shan, Erfang
    Cheng, T. C. E.
    Kang, Liying
    INFORMATION PROCESSING LETTERS, 2007, 105 (01) : 6 - 11
  • [4] On the domination numbers of generalized de Bruijn digraphs and generalized Kautz digraphs
    Kikuchi, Y
    Shibata, Y
    INFORMATION PROCESSING LETTERS, 2003, 86 (02) : 79 - 85
  • [5] Efficient absorbants in generalized de Bruijn digraphs
    Shiau, Alexander Chane
    Shiau, Tzong-Huei
    Wang, Yue-Li
    DISCRETE OPTIMIZATION, 2017, 25 : 77 - 85
  • [6] The Absorbant Number of Generalized de Bruijn Digraphs
    Kuo, Jyhmin
    Fu, Hung-Lin
    ARS COMBINATORIA, 2015, 118 : 433 - 443
  • [7] Distance domination of generalized de Bruijn and Kautz digraphs
    Yanxia Dong
    Erfang Shan
    Xiao Min
    Frontiers of Mathematics in China, 2017, 12 : 339 - 357
  • [8] Counting small cycles in generalized de Bruijn digraphs
    Hasunuma, T
    Shibata, Y
    NETWORKS, 1997, 29 (01) : 39 - 47
  • [9] On efficient absorbant conjecture in generalized De Bruijn digraphs
    Wu, Kuo-Hua
    Wang, Yue-Li
    Kloks, Ton
    INTERNATIONAL JOURNAL OF COMPUTER MATHEMATICS, 2017, 94 (05) : 922 - 932
  • [10] Distance domination of generalized de Bruijn and Kautz digraphs
    Dong, Yanxia
    Shan, Erfang
    Min, Xiao
    FRONTIERS OF MATHEMATICS IN CHINA, 2017, 12 (02) : 339 - 357
12345