DISCRIMINATING CODES IN BIPARTITE GRAPHS: BOUNDS, EXTREMAL CARDINALITIES, COMPLEXITY

被引：20
|
作者：
Charbit, Emmanuel [1 ]
Charon, Irene [1 ,2 ]
Cohen, Gerard [1 ,2 ]
Hudry, Olivier [1 ,2 ]
Lobstein, Antoine [1 ,2 ]
机构：
[1] TELECOM ParisTech, Inst TELECOM, F-75634 Paris 13, France
[2] CNRS, LTCI, UMR 5141, F-75634 Paris 13, France
来源：
ADVANCES IN MATHEMATICS OF COMMUNICATIONS | 2008年 / 2卷 / 04期
关键词：
Graph theory; bipartite graphs; discriminating codes; identifying codes; locating-dominating codes; separating codes; complexity;
D O I：
10.3934/amc.2008.2.403
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
Consider an undirected bipartite graph G = (V = I boolean OR A, E), with no edge inside I nor A. For any vertex v is an element of V, let N(v) be the set of neighbours of v. A code C subset of A is said to be discriminating if all the sets N(i) boolean AND C, i is an element of I, are nonempty and distinct. We study some properties of discriminating codes. In particular, we give bounds on the minimum size of these codes, investigate graphs where minimal discriminating codes have size close to the upper bound, or give the exact minimum size in particular graphs; we also give an NP-completeness result.
引用
收藏
页码：403 / 420
页数：18
相关论文
共 36 条
  • [1] Locating-dominating codes: Bounds and extremal cardinalities
    Caceres, Jose
    Hernando, Carmen
    Mora, Merce
    Pelayo, Ignacio M.
    Luz Puertas, Maria
    APPLIED MATHEMATICS AND COMPUTATION, 2013, 220 : 38 - 45
  • [2] Extremal cardinalities for identifying and locating-dominating codes in graphs
    Charon, Irene
    Hudry, Olivier
    Lobstein, Antoine
    DISCRETE MATHEMATICS, 2007, 307 (3-5) : 356 - 366
  • [3] Entropy/length profiles, bounds on the minimal covering of bipartite graphs, and trellis complexity of nonlinear codes
    Reuven, I
    Be'ery, Y
    IEEE TRANSACTIONS ON INFORMATION THEORY, 1998, 44 (02) : 580 - 598
  • [4] Bounds and Extremal Graphs for Total Dominating Identifying Codes
    Foucaud, Florent
    Lehtila, Tuomo
    ELECTRONIC JOURNAL OF COMBINATORICS, 2023, 30 (03) : 1 - 30
  • [5] Complexity results for identifying codes in planar graphs
    Auger, David
    Charon, Irene
    Hudry, Olivier
    Lobstein, Antoine
    INTERNATIONAL TRANSACTIONS IN OPERATIONAL RESEARCH, 2010, 17 (06) : 691 - 710
  • [6] On Extremal Bipartite Graphs with a Given Connectivity
    Chen, Hanlin
    Deng, Hanyuan
    Wu, Renfang
    FILOMAT, 2019, 33 (06) : 1531 - 1540
  • [7] Identifying codes in bipartite graphs of given maximum degree
    Chakraborty, Dipayan
    Foucaud, Florent
    Lehtila, Tuomo
    XII LATIN-AMERICAN ALGORITHMS, GRAPHS AND OPTIMIZATION SYMPOSIUM, LAGOS 2023, 2023, 224 : 157 - 165
  • [8] On extremal bipartite graphs with given number of cut edges
    Chen, Hanlin
    Wu, Renfang
    DISCRETE MATHEMATICS ALGORITHMS AND APPLICATIONS, 2020, 12 (02)
  • [9] Constructions of Binary Codes Based on Bipartite Graphs
    Wong, Denis C. K.
    MATHEMATICS IN COMPUTER SCIENCE, 2016, 10 (02) : 223 - 227
  • [10] Extremal values of degree-based entropies of bipartite graphs
    Cambie, Stijn
    Dong, Yanni
    Mazzamurro, Matteo
    INFORMATION SCIENCES, 2024, 676
1234