Discriminating codes in (bipartite) planar graphs

Irène Charon; Gérard Cohen; Olivier Hudry; Antoine Lobstein

doi:10.1016/j.ejc.2007.05.006

Discriminating codes in (bipartite) planar graphs

Irène Charon
, Gérard Cohen
, Olivier Hudry
, Antoine Lobstein

Research output: Contribution to journal › Article › peer-review

Abstract

Consider a connected undirected bipartite graph G = (V = I ∪ A, E), with no edges inside I or A. For any vertex v ∈ V, let N (v) be the set of neighbours of v. A code C ⊆ A is said to be discriminating if all the sets N (i) ∩ C, i ∈ I, are nonempty and distinct. We study some properties of discriminating codes in particular classes of bipartite graphs, namely trees and, more generally, (bipartite) planar graphs.

Original language	English
Pages (from-to)	1353-1364
Number of pages	12
Journal	European Journal of Combinatorics
Volume	29
Issue number	5
DOIs	https://doi.org/10.1016/j.ejc.2007.05.006
Publication status	Published - 1 Jul 2008

Access to Document

10.1016/j.ejc.2007.05.006

Cite this

@article{726b3cafca2b45b092e4bfefde34dace,

title = "Discriminating codes in (bipartite) planar graphs",

abstract = "Consider a connected undirected bipartite graph G = (V = I ∪ A, E), with no edges inside I or A. For any vertex v ∈ V, let N (v) be the set of neighbours of v. A code C ⊆ A is said to be discriminating if all the sets N (i) ∩ C, i ∈ I, are nonempty and distinct. We study some properties of discriminating codes in particular classes of bipartite graphs, namely trees and, more generally, (bipartite) planar graphs.",

author = "Ir{\`e}ne Charon and G{\'e}rard Cohen and Olivier Hudry and Antoine Lobstein",

year = "2008",

month = jul,

day = "1",

doi = "10.1016/j.ejc.2007.05.006",

language = "English",

volume = "29",

pages = "1353--1364",

journal = "European Journal of Combinatorics",

issn = "0195-6698",

number = "5",

}

TY - JOUR

T1 - Discriminating codes in (bipartite) planar graphs

AU - Charon, Irène

AU - Cohen, Gérard

AU - Hudry, Olivier

AU - Lobstein, Antoine

PY - 2008/7/1

Y1 - 2008/7/1

N2 - Consider a connected undirected bipartite graph G = (V = I ∪ A, E), with no edges inside I or A. For any vertex v ∈ V, let N (v) be the set of neighbours of v. A code C ⊆ A is said to be discriminating if all the sets N (i) ∩ C, i ∈ I, are nonempty and distinct. We study some properties of discriminating codes in particular classes of bipartite graphs, namely trees and, more generally, (bipartite) planar graphs.

AB - Consider a connected undirected bipartite graph G = (V = I ∪ A, E), with no edges inside I or A. For any vertex v ∈ V, let N (v) be the set of neighbours of v. A code C ⊆ A is said to be discriminating if all the sets N (i) ∩ C, i ∈ I, are nonempty and distinct. We study some properties of discriminating codes in particular classes of bipartite graphs, namely trees and, more generally, (bipartite) planar graphs.

U2 - 10.1016/j.ejc.2007.05.006

DO - 10.1016/j.ejc.2007.05.006

M3 - Article

AN - SCOPUS:42649108394

SN - 0195-6698

VL - 29

SP - 1353

EP - 1364

JO - European Journal of Combinatorics

JF - European Journal of Combinatorics

IS - 5

ER -

Discriminating codes in (bipartite) planar graphs

Abstract

Access to Document

Fingerprint

Cite this