On three domination-based identification problems in block graphs
| Autor: | Chakraborty, Dipayan, Foucaud, Florent, Parreau, Aline, Wagler, Annegret |
|---|---|
| Přispěvatelé: | Laboratoire d'Informatique, de Modélisation et d'Optimisation des Systèmes (LIMOS), Ecole Nationale Supérieure des Mines de St Etienne (ENSM ST-ETIENNE)-Centre National de la Recherche Scientifique (CNRS)-Université Clermont Auvergne (UCA)-Institut national polytechnique Clermont Auvergne (INP Clermont Auvergne), Université Clermont Auvergne (UCA)-Université Clermont Auvergne (UCA), Graphes, AlgOrithmes et AppLications (GOAL), Laboratoire d'InfoRmatique en Image et Systèmes d'information (LIRIS), Université Lumière - Lyon 2 (UL2)-École Centrale de Lyon (ECL), Université de Lyon-Université de Lyon-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Institut National des Sciences Appliquées de Lyon (INSA Lyon), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Centre National de la Recherche Scientifique (CNRS)-Université Lumière - Lyon 2 (UL2)-École Centrale de Lyon (ECL), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Centre National de la Recherche Scientifique (CNRS), ANR-16-IDEX-0001,CAP 20-25,CAP 20-25(2016), ANR-10-LABX-0016,IMoBS3,Innovative Mobility : Smart and Sustainable Solutions(2010), ANR-21-CE48-0004,GRALMECO,Algorithmique des problèmes de couverture métriques dans les graphes(2021), Parreau, Aline, CAP 20-25 - - CAP 20-252016 - ANR-16-IDEX-0001 - IDEX - VALID, Laboratoires d'excellence - Innovative Mobility : Smart and Sustainable Solutions - - IMoBS32010 - ANR-10-LABX-0016 - LABX - VALID, Algorithmique des problèmes de couverture métriques dans les graphes - - GRALMECO2021 - ANR-21-CE48-0004 - AAPG2021 - VALID |
| Rok vydání: | 2018 |
| Předmět: |
FOS: Computer and information sciences
Discrete Mathematics (cs.DM) domination number block graph order of a graph [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM] [MATH.MATH-CO] Mathematics [math]/Combinatorics [math.CO] [INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM] identifying code maximal clique articulation Identifying codes [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO] FOS: Mathematics Mathematics - Combinatorics Locating-dominating codes Combinatorics (math.CO) block graphs locating-dominating Computer Science - Discrete Mathematics MathematicsofComputing_DISCRETEMATHEMATICS |
| DOI: | 10.48550/arxiv.1811.09537 |
| Popis: | The problems of determining the minimum-sized \emph{identifying}, \emph{locating-dominating} and \emph{open locating-dominating codes} of an input graph are special search problems that are challenging from both theoretical and computational viewpoints. In these problems, one selects a dominating set $C$ of a graph $G$ such that the vertices of a chosen subset of $V(G)$ (i.e. either $V(G)\setminus C$ or $V(G)$ itself) are uniquely determined by their neighborhoods in $C$. A typical line of attack for these problems is to determine tight bounds for the minimum codes in various graphs classes. In this work, we present tight lower and upper bounds for all three types of codes for \emph{block graphs} (i.e. diamond-free chordal graphs). Our bounds are in terms of the number of maximal cliques (or \emph{blocks}) of a block graph and the order of the graph. Two of our upper bounds verify conjectures from the literature - with one of them being now proven for block graphs in this article. As for the lower bounds, we prove them to be linear in terms of both the number of blocks and the order of the block graph. We provide examples of families of block graphs whose minimum codes attain these bounds, thus showing each bound to be tight. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|