Optimal Identifying Codes in Cycles and Paths

被引：12
作者：
Junnila, Ville [1 ]
Laihonen, Tero [1 ]
机构：
[1] Univ Turku, Dept Math, TUCS, Turku 20014, Finland
来源：
GRAPHS AND COMBINATORICS | 2012年 / 28卷 / 04期
基金：
芬兰科学院;
关键词：
Identifying code; Optimal code; Cycle; Path;
D O I：
10.1007/s00373-011-1058-6
中图分类号：
O1 [数学];
学科分类号：
0701 ; 070101 ;
摘要：
The concept of identifying codes in a graph was introduced by Karpovsky et al. (in IEEE Trans Inf Theory 44(2):599-611, 1998). These codes have been studied in several types of graphs such as hypercubes, trees, the square grid, the triangular grid, cycles and paths. In this paper, we determine the optimal cardinalities of identifying codes in cycles and paths in the remaining open cases.
引用
收藏
页码：469 / 481
页数：13
相关论文
共 50 条
  • [1] Optimal Identifying Codes in Cycles and Paths
    Ville Junnila
    Tero Laihonen
    Graphs and Combinatorics, 2012, 28 : 469 - 481
  • [2] Identifying Codes in the Complementary Prism of Cycles
    Cappelle, Marcia R.
    Coelho, Erika M. M.
    Coelho, Hebert
    Penso, Lucia D.
    Rautenbach, Dieter
    ELECTRONIC NOTES IN THEORETICAL COMPUTER SCIENCE, 2019, 346 : 241 - 251
  • [3] Paths and cycles identifying vertices in twisted cubes
    Lai, Pao-Lien
    APPLIED MATHEMATICS AND COMPUTATION, 2015, 259 : 620 - 627
  • [4] Sequences of optimal identifying codes
    Laihonen, TK
    IEEE TRANSACTIONS ON INFORMATION THEORY, 2002, 48 (03) : 774 - 776
  • [5] Optimal orientations of products of paths and cycles
    Koh, KM
    Tay, EG
    DISCRETE APPLIED MATHEMATICS, 1997, 78 (1-3) : 163 - 174
  • [6] A family of optimal identifying codes in Z2
    Honkala, Iiro
    JOURNAL OF COMBINATORIAL THEORY SERIES A, 2006, 113 (08) : 1760 - 1763
  • [7] Broadcasts on paths and cycles
    Bouchouika, Sabrina
    Bouchemakh, Isma
    Sopena, Eric
    DISCRETE APPLIED MATHEMATICS, 2020, 283 : 375 - 395
  • [8] Paths and cycles of hypergraphs
    Wang, JF
    Lee, TT
    SCIENCE IN CHINA SERIES A-MATHEMATICS, 1999, 42 (01): : 1 - 12
  • [9] ON THE SPECTRA OF CYCLES AND PATHS
    Celik, F.
    Cangul, I. N.
    TWMS JOURNAL OF APPLIED AND ENGINEERING MATHEMATICS, 2019, 9 (03): : 571 - 580
  • [10] Paths and cycles of hypergraphs
    王建方
    Tony T.Lee
    Science China Mathematics, 1999, (01) : 1 - 12
12345