Characterizing extremal digraphs for identifying codes and extremal cases of Bondys theorem on induced subsetsReportar como inadecuado




Characterizing extremal digraphs for identifying codes and extremal cases of Bondys theorem on induced subsets - Descarga este documento en PDF. Documentación en PDF para descargar gratis. Disponible también para leer online.

1 LaBRI - Laboratoire Bordelais de Recherche en Informatique 2 LRI - Laboratoire de Recherche en Informatique 3 IF - Institut Fourier

Abstract : An identifying code of a digraph $G$ is a dominating subset $C$ of the vertices of $G$ such that all distinct vertices of $G$ have distinct inneighbourhoods within $C$. In this paper, we classify all finite digraphs which only admit their whole vertex set in any identifying code. We also classify all such infinite oriented graphs. Furthermore, by relating this concept to a well known theorem of A.~Bondy on set systems we classify the extremal cases for this theorem.

Keywords : Digraphs Identifying codes Dominating sets Infinite digraphs Induced sets





Autor: Florent Foucaud - Reza Naserasr - Aline Parreau -

Fuente: https://hal.archives-ouvertes.fr/



DESCARGAR PDF




Documentos relacionados