Advanced Search
Article Contents
Article Contents

Discriminating codes in bipartite graphs: bounds, extremal cardinalities, complexity

Abstract / Introduction Related Papers Cited by
  • Consider an undirected bipartite graph $G=(V=I\cup A,E)$, with no edge inside $I$ nor $A$. For any vertex $v\in V$, let $N(v)$ be the set of neighbours of $v$. A code $C \subseteq A$ is said to be discriminating if all the sets $N(i) \cap C$, $i \in 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.
    Mathematics Subject Classification: Primary: 05C99; Secondary: 94B65, 05C35, 68Q17.


    \begin{equation} \\ \end{equation}
  • 加载中

Article Metrics

HTML views() PDF downloads(166) Cited by(0)

Access History



    DownLoad:  Full-Size Img  PowerPoint