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 条
  • [21] Minimum identifying codes in some graphs differing by matchings
    Nikandish, R.
    Nasab, O. Khani
    Dodonge, E.
    DISCRETE MATHEMATICS ALGORITHMS AND APPLICATIONS, 2020, 12 (03)
  • [22] On paths and cycles through specified vertices
    Harant, J
    DISCRETE MATHEMATICS, 2004, 286 (1-2) : 95 - 98
  • [23] Outerplanar Turan numbers of cycles and paths
    Fang, Longfei
    Zhai, Mingqing
    DISCRETE MATHEMATICS, 2023, 346 (12)
  • [24] BLOCKING SETS FOR CYCLES AND PATHS DESIGNS
    Bonacini, Paola
    Marino, Lucia
    APPLICABLE ANALYSIS AND DISCRETE MATHEMATICS, 2020, 14 (01) : 183 - 197
  • [25] Pm ∨ Pk-equipackable paths and cycles
    Zhang, Liandi
    Wang, Yanfei
    Zhang, Yuqin
    ARS COMBINATORIA, 2017, 130 : 417 - 425
  • [26] Powers of cycles, powers of paths, and distance graphs
    Lin, Min Chih
    Rautenbach, Dieter
    Soulignac, Francisco Juan
    Szwarcfiter, Jayme Luiz
    DISCRETE APPLIED MATHEMATICS, 2011, 159 (07) : 621 - 627
  • [27] Decomposition of complete bipartite graphs into paths and cycles
    Jeevadoss, S.
    Muthusamy, A.
    DISCRETE MATHEMATICS, 2014, 331 : 98 - 108
  • [28] Pm ∨ Pk-equicoverable paths and cycles
    Zhang, Liandi
    Zhang, Yuqin
    ARS COMBINATORIA, 2020, 149 : 15 - 21
  • [29] ON THE NUMBER OF INCREASING PATHS IN LABELED CYCLES AND STARS
    Chen Lei Lü Changhong Ye Yongsheng Department of Mathematics
    AppliedMathematics:AJournalofChineseUniversities(SeriesB), 2007, (01) : 1 - 6
  • [30] The number of completely different optimal identifying codes in the infinite square grid
    Pelto, Mikko
    DISCRETE APPLIED MATHEMATICS, 2017, 233 : 143 - 158
12345