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 条

[21] Lower Bounds on the Graphical Complexity of Finite-Length LDPC Codes
Sason, Igal
2009 IEEE INTERNATIONAL SYMPOSIUM ON INFORMATION THEORY, VOLS 1- 4, 2009, : 219 - 223
[22] The extremal values of some topological indices in bipartite graphs with a given matching number
Chen, Hanlin
Wu, Renfang
Deng, Hanyuan
APPLIED MATHEMATICS AND COMPUTATION, 2016, 280 : 103 - 109
[23] Weighted coloring on planar, bipartite and split graphs: Complexity and approximation
de Werra, D.
Demange, M.
Escoffier, B.
Monnot, J.
Paschos, V. Th.
DISCRETE APPLIED MATHEMATICS, 2009, 157 (04) : 819 - 832
[24] Clustering bipartite and chordal graphs: Complexity, sequential and parallel algorithms
Abbas, N
Stewart, L
DISCRETE APPLIED MATHEMATICS, 1999, 91 (1-3) : 1 - 23
[25] Sharp upper bounds for Zagreb indices of bipartite graphs with a given diameter
Li, Shuchao
Zhang, Minjie
APPLIED MATHEMATICS LETTERS, 2011, 24 (02) : 131 - 137
[26] On the complexity of finding chordless paths in bipartite graphs and some interval operators in graphs and hypergraphs
Mezzini, Mauro
THEORETICAL COMPUTER SCIENCE, 2010, 411 (7-9) : 1212 - 1220
[27] Sharp upper bounds for multiplicative Zagreb indices of bipartite graphs with given diameter
Wang, Chunxiang
Liu, Jia-Bao
Wang, Shaohui
DISCRETE APPLIED MATHEMATICS, 2017, 227 : 156 - 165
[28] Sharp bounds for the number of 3-independent partitions and the chromaticity of bipartite graphs
Dong, FM
Koh, KM
Teo, KL
Little, CHC
Hendy, MD
JOURNAL OF GRAPH THEORY, 2001, 37 (01) : 48 - 77
[29] The complexity of the L(p, q)-labeling problem for bipartite planar graphs of small degree
Janczewski, Robert
Kosowski, Adrian
Malafiejski, Michal
DISCRETE MATHEMATICS, 2009, 309 (10) : 3270 - 3279
[30] On achievable rates and complexity of LDPC codes over parallel channels: Bounds and applications
Sason, Igal
Wiechman, Gil
IEEE TRANSACTIONS ON INFORMATION THEORY, 2007, 53 (02) : 580 - 598

← 1 2 3 4 →