Search results for: KODY IDENTYFIKUJĄCE

• On the size of identifying codes in triangle-free graphs

  Publication

  • F. Foucaud
  • R. Klasing
  • A. Kosowski
  • A. Raspaud

  - DISCRETE APPLIED MATHEMATICS - Year 2012

  In an undirected graph G, a subset C⊆V(G) such that C is a dominating set of G, and each vertex in V(G) is dominated by a distinct subset of vertices from C, is called an identifying code of G. The concept of identifying codes was introduced by Karpovsky, Chakrabarty and Levitin in 1998. For a given identifiable graph G, let gammaID(G) be the minimum cardinality of an identifying code in G. In this paper, we show that for any connected...

  Full text available to download