On three domination-based identification problems in block graphs

DOI10.1007/978-3-031-25211-2_21MaRDI QIDQ6132542zbMATH OpenOpenAlexFDO

Authors Dipayan Chakraborty, Florent Foucaud, Aline Parreau, Annegret K. Wagler

Publication date 17 August 2023

Published in Algorithms and Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1811.09537

zbMATH Keywords

articulationblock graphdomination numberidentifying codelocating-dominatingmaximal cliqueorder of a graph

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Abstract: 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)setminusC$ 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.

Cites work

• A Characterization of Block-Graphs
• Characterizing extremal graphs for open neighbourhood location-domination
• Decision and approximation complexity for identifying codes and locating-dominating sets in restricted graph classes
• Distinguishing-transversal in hypergraphs and identifying open codes in cubic graphs
• Domination and location in acyclic graphs
• scientific article; zbMATH DE number 3161569 (Why is no real title available?)
• scientific article; zbMATH DE number 5717189 (Why is no real title available?)
• scientific article; zbMATH DE number 3906528 (Why is no real title available?)
• scientific article; zbMATH DE number 2147927 (Why is no real title available?)
• Identification, location-domination and metric dimension on interval and permutation graphs. I: Bounds.
• Identification, location-domination and metric dimension on interval and permutation graphs. II: Algorithms and complexity
• Identifying codes in hereditary classes of graphs and VC-dimension
• Identifying codes in line graphs
• Linear-time algorithms for three domination-based separation problems in block graphs
• Locating-dominating sets and identifying codes in graphs of girth at least 5
• Location-domination and matching in cubic graphs
• Minimizing the size of an identifying or locating-dominating code in a graph is NP-hard.
• On a new class of codes for identifying vertices in graphs
• On metric properties of certain clique graphs
• Revisiting and improving upper bounds for identifying codes
• Study of identifying code polyhedra for some families of split graphs
• The difference between the metric dimension and the determining number of a graph
• The identifying code, the locating-dominating, the open locating-dominating and the locating total-dominating problems under some graph operations

Cited in

(1)

• On three domination-based identification problems in block graphs

This page was built for publication: On three domination-based identification problems in block graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6132542)