Discriminating codes in (bipartite) planar graphs
| Autor: | Gérard D. Cohen, Antoine Lobstein, Olivier Hudry, Irène Charon |
|---|---|
| Rok vydání: | 2008 |
| Předmět: |
Discrete mathematics
Robertson–Seymour theorem Complete bipartite graph Theoretical Computer Science Combinatorics Computational Theory and Mathematics Edge-transitive graph Computer Science::Discrete Mathematics TheoryofComputation_ANALYSISOFALGORITHMSANDPROBLEMCOMPLEXITY Triangle-free graph Bipartite graph Computer Science::General Literature Discrete Mathematics and Combinatorics Maximal independent set Geometry and Topology Pancyclic graph MathematicsofComputing_DISCRETEMATHEMATICS Computer Science::Cryptography and Security Mathematics Forbidden graph characterization |
| Zdroj: | European Journal of Combinatorics. 29:1353-1364 |
| ISSN: | 0195-6698 |
| Popis: | Consider a connected undirected bipartite graph G=([email protected]?A,E), with no edges inside I or A. For any vertex [email protected]?V, let N(v) be the set of neighbours of v. A code [email protected]?A is said to be discriminating if all the sets N(i)@?C, [email protected]?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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect