On three domination-based identification problems in block graphs

• Autorzy: Chakraborty, Dipayan , Foucaud, Florent , Parreau, Aline , Wagler, Annegret
• Języki publikacji: EN

Abstrakty

EN

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

Słowa kluczowe

EN

identifying code; locating-dominating code; open locating-dominating code; block graph

• Czasopismo: Fundamenta Informaticae
• Rocznik: 2024
• Tom: Vol. 191, nr 3-4
• Strony: 197--229
• Opis fizyczny: Bibliogr. 39 poz., rys.

Twórcy

autor

Chakraborty, Dipayan

• Université Clermont-Auvergne, CNRS Mines de Saint- Étienne, Clermont-Auvergne-INP LIMOS, 63000 Clermont-Ferrand, France,

autor

Foucaud, Florent

• Université Clermont-Auvergne, CNRS Mines de Saint- Étienne, Clermont-Auvergne-INP LIMOS, 63000 Clermont-Ferrand, France,

autor

Parreau, Aline

• Univ Lyon, CNRS, INSA Lyon, UCBL Centrale Lyon, Univ Lyon 2, LIRIS, UMR5205 69622 Villeurbanne Cedex, France,

autor

Wagler, Annegret

• Université Clermont-Auvergne, CNRS Mines de Saint- Étienne, Clermont-Auvergne-INP LIMOS, 63000 Clermont-Ferrand, France ,

Bibliografia

• [1] Jean D, Lobstein A. Watching systems, identifying, locating-dominating and discriminating codes in graphs: a bibliography. Published electronically at https://dragazo.github.io/bibdom/main.pdf, 2012.
• [2] Rényi A. On random generating elements of a finite Boolean algebra. Acta Scientiarum Mathematicarum Szeged, 1961. 22:75-81.
• [3] Rao N. Computational complexity issues in operative diagnosis of graph-based systems. IEEE Transactions on Computers, 1993. 42(4):447-457. doi:10.1109/12.214691.
• [4] Moret BME, Shapiro HD. On Minimizing a Set of Tests. SIAM Journal on Scientific and Statistical Computing, 1985. 6(4):983-1003. doi:10.1137/090606.
• [5] Chlebus BS, Nguyen SH. On Finding Optimal Discretizations for Two Attributes. In: Proceedings of the First International Conference on Rough Sets and Current Trends in Computing, volume 1424. Springer Berlin Heidelberg, Berlin, Heidelberg, 1998 pp. 537-544. doi:10.1007/3-540-69115-4 74.
• [6] Karpovsky MG, Chakrabarty K, Levitin LB. On a new class of codes for identifying vertices in graphs. IEEE transactions on information theory, 1998. 44(2):599-611. doi:10.1109/18.661507.
• [7] Slater PJ. Domination and location in acyclic graphs. Networks, 1987. 17(1):55-64. doi:10.1002/net.3230170105.
• [8] Slater PJ. Dominating and reference sets in a graph. Journal of Mathematical and Physical Sciences, 1988. 22(4):445-455.
• [9] Seo SJ, Slater PJ. Open neighborhood locating dominating sets. Australasian Journal of Combinatorics, 2010. 46:109-120.
• [10] Henning MA, Yeo A. Total domination in graphs. Springer, 2013. doi:10.1007/978-1-4614-6525-6.
• [11] Charon I, Hudry O, Lobstein A. Minimizing the size of an identifying or locating-dominating code in a graph is NP-hard. Theoretical Computer Science, 2003. 290(3):2109-2120. doi:10.1016/S0304-3975(02)00536-4.
• [12] Foucaud F, Mertzios GB, Naserasr R, Parreau A, Valicov P. Identification, location-domination and metric dimension on interval and permutation graphs. II. Algorithms and complexity. Algorithmica, 2017. 78(3):914-944. doi:10.1007/s00453-016-0184-1.
• [13] Foucaud F. Decision and approximation complexity for identifying codes and locating-dominating sets in restricted graph classes. J. Discrete Algorithms, 2015. 31:48-68. doi:10.1016/j.jda.2014.08.004.
• [14] Pandey A. Open Neighborhood Locating-Dominating Set in Graphs: Complexity and Algorithms. In: Proceedings of the 14th International Conference on Information Technology (ICIT 2015). 2015 pp. 1-6. doi:10.1109/ICIT.2015.14.
• [15] Bertrand N, Charon I, Hudry O, Lobstein A. Identifying and locating-dominating codes on chains and cycles. European Journal of Combinatorics, 2004. 25(7):969-987. doi:10.1016/j.ejc.2003.12.013.
• [16] Gravier S, Moncel J. On graphs having a V\{x} set as an identifying code. Discrete Mathematics, 2007. 307(3-5):432-434. doi:10.1016/j.disc.2005.09.035.
• [17] Argiroffo GR, Bianchi SM, Lucarini Y, Wagler AK. Polyhedra associated with identifying codes. Discrete Applied Mathematics, 2018. 245:16-27. doi:10.1016/j.dam.2017.06.005.
• [18] Argiroffo GR, Bianchi SM, Lucarini Y, Wagler AK. Polyhedra associated with locating-dominating, open locating-dominating and locating total-dominating sets in graphs. Discrete Applied Mathematics, 2022. 322:465-480. doi:10.1016/j.dam.2022.06.025.
• [19] Argiroffo GR, Bianchi SM, Wagler AK. Study of identifying code polyhedra for some families of split graphs. In: International Symposium on Combinatorial Optimization. Springer, 2014 pp. 13-25. doi:10.1007/978-3-319-09174-7 2.
• [20] Foucaud F, Mertzios GB, Naserasr R, Parreau A, Valicov P. Identification, location-domination and metric dimension on interval and permutation graphs. I. Bounds. Theoretical Computer Science, 2017. 668:43-58. doi:10.1016/j.tcs.2017.01.006.
• [21] Bertrand N, Charon I, Hudry O, Lobstein A. 1-identifying codes on trees. Australas. J Comb., 2005. 31:21-36.
• [22] Foucaud F, Gravier S, Naserasr R, Parreau A, Valicov P. Identifying codes in line graphs. Journal of Graph Theory, 2013. 73(4):425-448. doi:10.1002/jgt.21686.
• [23] Rall DF, Slater PJ. On location-domination numbers for certain classes of graphs. Congressus Numerantium, 1984. 45:97-106.
• [24] Bousquet N, Lagoutte A, Li Z, Parreau A, Thomassé S. Identifying codes in hereditary classes of graphs and VC-dimension. SIAM Journal on Discrete Mathematics, 2015. 29(4):2047-2064. doi:10.1137/14097879X.
• [25] Balbuena C, Foucaud F, Hansberg A. Locating-dominating sets and identifying codes in graphs of girth at least 5. The Electronic Journal of Combinatorics, 2015. 22(2):P2.15. doi:10.37236/4562.
• [26] Foucaud F, Lehtilӓ T. Revisiting and improving upper bounds for identifying codes. SIAM Journal on Discrete Mathematics, 2022. doi:10.1137/22M148999X
• [27] Foucaud F, Perarnau G. Bounds on identifying codes in terms of degree parameters. The Electronic Journal of Combinatorics, 2012. 19(1):P32. doi:10.37236/2036.
• [28] Foucaud F, Henning MA. Location-domination and matching in cubic graphs. Discrete Mathematics, 2016. 339(4):1221-1231. doi:10.1016/j.disc.2015.11.016.
• [29] Garijo D, Gonz´alez A, M´arquez A. The difference between the metric dimension and the determining number of a graph. Applied Mathematics and Computation, 2014. 249:487-501. doi:10.1016/j.amc.2014.10.034.
• [30] Henning MA, Yeo A. Distinguishing-Transversal in Hypergraphs and Identifying Open Codes in Cubic Graphs. Graphs and Combinatorics, 2014. 30:909-932. doi:10.1007/s00373-013-1311-2.
• [31] Harary F. A Characterization of Block-Graphs. Canadian Mathematical Bulletin, 1963. 6(1):1-6. doi:10.4153/CMB-1963-001-x.
• [32] Howorka E. On metric properties of certain clique graphs. Journal of Combinatorial Theory, Series B, 1979. 27(1):67-74. doi:10.1016/0095-8956(79)90069-8.
• [33] Bandelt HJ, Mulder HM. Distance-hereditary graphs. Journal of Combinatorial Theory, Series B, 1986. 41(2):182-208. doi:10.1016/0095-8956(86)90043-2.
• [34] Argiroffo GR, Bianchi SM, Lucarini Y, Wagler AK. Linear-time algorithms for three domination-based separation problems in block graphs. Discrete Applied Mathematics, 2020. 281:6-41. doi:10.1016/j.dam.2019.08.001.
• [35] Argiroffo GR, Bianchi SM, Lucarini Y, Wagler AK. On the identifying code number of block graphs. In: Proceedings of ICGT 2018, Lyon, France. 2018 .
• [36] Chakraborty D, Foucaud F, Parreau A, Wagler AK. On Three Domination-Based Identification Problems in Block Graphs. In: Bagchi A, Muthu R (eds.), Algorithms and Discrete Applied Mathematics - 9th International Conference, CALDAM 2023, Gandhinagar, India, February 9-11, 2023, Proceedings, volume 13947 of Lecture Notes in Computer Science. Springer, 2023 pp. 271-283. doi:10.1007/978-3-031-25211-2 21.
• [37] Foucaud F, Guerrini E, Kovše M, Naserasr R, Parreau A, Valicov P. Extremal graphs for the identifying code problem. European Journal of Combinatorics, 2011. 32(4):628-638. doi:10.1016/j.ejc.2011.01.002.
• [38] Foucaud F, Ghareghani N, Roshany-Tabrizi A, Sharifani P. Characterizing extremal graphs for open neighbourhood location-domination. Discrete Applied Mathematics, 2021. 302:76-79. doi:10.1016/j.dam.2021.06.006.
• [39] Erdõs P. Some combinatorial, geometric and set theoretic problems in measure theory. In: Measure Theory Oberwolfach 1983. Springer, 1984 pp. 321-327.

Identyfikatory

DOI

10.3233/FI-242179