On Three Domination-based Identification Problems in Block Graphs

Issue title: Codes, Graphs, Coverings, and Identification: Special Issue Honoring the 60-th Birthday of Professor Iiro Honkala

Guest editors: Vesa Halava, Jarkko Kari and Tero Laihonen

Article type: Research Article

Authors: Chakraborty, Dipayan^{a; *; †} | Foucaud, Florent^b | Parreau, Aline^c | Wagler, Annegret^d

Affiliations: [a] Université Clermont-Auvergne, CNRS, Mines de Saint-Étienne, Clermont-Auvergne-INP, LIMOS, 63000 Clermont-Ferrand, France. [email protected] | [b] Université Clermont-Auvergne, CNRS, Mines de Saint-Étienne, Clermont-Auvergne-INP, LIMOS, 63000 Clermont-Ferrand, France. [email protected] | [c] Univ Lyon, CNRS, INSA Lyon, UCBL, Centrale Lyon, Univ Lyon 2, LIRIS, UMR5205, 69622 Villeurbanne Cedex, France. [email protected] | [d] Université Clermont-Auvergne, CNRS, Mines de Saint-Étienne, Clermont-Auvergne-INP, LIMOS, 63000 Clermont-Ferrand, France. [email protected]

Correspondence: [†] Address for correspondence: LIMOS, 1 rue de la Chebarde, Campus des Cézeaux, 63178 Aubière Cedex, France

Note: [*] Also works: Department of Mathematics and Applied Mathematics, University of Johannesburg, Auckland Park, 2006, South Africa

Abstract: The problems of determining the minimum-sized identifying, locating-dominating and 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) \ 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 graph classes. In this work, we present tight lower and upper bounds for all three types of codes for block graphs (i.e. diamond-free chordal graphs). Our bounds are in terms of the number of maximal cliques (or 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.

Keywords: identifying code, locating-dominating code, open locating-dominating code, block graph

DOI: 10.3233/FI-242179

Journal: Fundamenta Informaticae, vol. 191, no. 3-4, pp. 197-229, 2024