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

Telecom Paris
CNRS

Résultats de recherche: Contribution à un journal › Article › Revue par des pairs

Résumé

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.

langue originale	Anglais
Pages (de - à)	1353-1364
Nombre de pages	12
journal	European Journal of Combinatorics
Volume	29
Numéro de publication	5
Les DOIs	https://doi.org/10.1016/j.ejc.2007.05.006
état	Publié - 1 juil. 2008

Accès au document

10.1016/j.ejc.2007.05.006

Autres fichiers et liens

Lien vers la publication dans Scopus

Contient cette citation

@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.

UR - https://www.scopus.com/pages/publications/42649108394

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

Résumé

Accès au document

Autres fichiers et liens

Empreinte digitale

Contient cette citation