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 条

[41] Spectral conditions for the existence of specified paths and cycles in graphs [J].

Zhai, Mingqing ;

Lin, Huiqiu ;

Gong, Shicai .

LINEAR ALGEBRA AND ITS APPLICATIONS, 2015, 471 :21-27

[42] Distance restricted optimal pebbling in paths [J].

Shiue, Chin-Lin .

DISCRETE APPLIED MATHEMATICS, 2021, 297 :46-54

[43] On identifying codes that are robust against edge changes [J].

Honkala, Iiro ;

Laihonen, Tero .

INFORMATION AND COMPUTATION, 2007, 205 (07) :1078-1095

[44] Parameterized Codes over Cycles [J].

Gonzalez Sarabia, Manuel ;

Lara, Joel Nava ;

Renteria Marques, Carlos ;

Sarmiento Rosales, Eliseo .

ANALELE STIINTIFICE ALE UNIVERSITATII OVIDIUS CONSTANTA-SERIA MATEMATICA, 2013, 21 (03) :241-255

[45] On the sigma chromatic number of the join of a finite number of paths and cycles [J].

Garciano, Agnes D. ;

Lagura, Maria Czarina T. ;

Marcelo, Reginaldo M. .

ASIAN-EUROPEAN JOURNAL OF MATHEMATICS, 2021, 14 (02)

[46] Diagnosability of the strong product of paths and cycles under PMC Model [J].

Chen, Bu ;

Li, Feng .

27TH IEEE/ACIS INTERNATIONAL SUMMER CONFERENCE ON SOFTWARE ENGINEERING ARTIFICIAL INTELLIGENCE NETWORKING AND PARALLEL/DISTRIBUTED COMPUTING, SNPD 2024-SUMMER, 2024, :211-216

[47] DECOMPOSITION OF COMPLETE TRIPARTITE GRAPHS INTO CYCLES AND PATHS OF LENGTH THREE [J].