On locating-dominating set of subgraph-amalgamation graphs

Darmaji Darmaji, Suhadi Wido Saputro

Abstract


The locating-dominating number of a graph G is defined as the minimum cardinality of W ⊆ V(G) such that for every two distinct vertices u, v ∈ V(G) ∖ W, ∅ ≠ NG(u) ∩ W ≠ NG(v) ∩ W ≠ ∅. For n ∈ ℕ and i ∈ {1, 2, …, n}, let Hi be a simple connected graph containing a connected subgraph J. Let ℋ = {H1, H2, …, Hn} be a finite collection of simple connected graphs. The subgraph-amalgamation of ℋ = {H1, H2, …, Hn} in J, denoted by Subgraph-Amal{ℋ; J}, is a graph obtained by identifying all elements of ℋ in J. The subgraph J is called as a terminal subgraph of ℋ. In this paper, we determine general bounds of the locating-dominating number of subgraph-amalgamation graphs for any connected terminal subgraphs. We also determine the locating-dominating number of the vertex-amalgamation graph, which is Subgraph-Amal{ℋ; J} where J is K1.

Keywords


locating-dominating number; locating-dominating set; subgraph-amalgamation graph; vertex-amalgamation graph

Full Text:

PDF

DOI: http://dx.doi.org/10.5614/ejgta.2026.14.2.7

References

G.R. Argiroffo, S.M. Bianchi, and A.K. Wagler, A polyhedral approach to locating-dominating sets in graphs, Electron. Notes Discrete Math., 50 (2015), 89–94.

G. Argiroffo, S. Bianchi, Y. Lucarini, and A. Wagler, The identifying code, the locating-dominating, the open locating-dominating and the locating total-dominating problems under some graph operations, Electron. Notes Theoret. Comput. Sci., 346 (2019), 135–145.

C. Balbuena, F. Foucaud, and A. Hansberg, Locating-dominating sets and identifying codes in graphs of girth at least 5, Electron. J. Combin., 22(2) (2015), P2.15.

N. Bertrand, I. Charon, O. Hudry, and A. Lobstein, Identifying and locating-dominating codes on chains and cycles, European J. Combin., 25(7) (2004), 969–987.

M. Blidia, M. Chellali, F. Maffray, J. Moncel, and A. Semri, Locating-domination and identifying codes in trees, Australasian J. Combin., 39 (2007), 219–232.

P. Boonmee, J. Ma-In, and S. Panma, Domination numbers of amalgamations of cycles at connected subgraphs, J. Math., 2022 (2022), Article ID 7336728.

J. Cáceres, C. Hernando, M. Mora, I.M. Pelayo, and M.L. Puertas, Locating-dominating codes: Bounds and extremal cardinalities, Appl. Math. Comput., 220 (2013), 38–45.

S.R. Canoy, Jr., G.A. Malacas, and D. Tarepe, Locating-dominating sets in graphs, Appl. Math. Sci., 8 No.8 (2014), 4381–4388.

M.R. Cappelle, G.C.M. Gomes, and V.F. dos Santos, Parameterized algorithms for locating-dominating sets, Procedia Comput. Sci., 195 (2021), 68–76.

I. Charon, O. Hudry, and A. Lobstein, Minimizing the size of an identifying or locating-dominating code in a graph is NP-hard, Theoret. Comput. Sci., 290(3) (2003), 2109–2120.

C.J. Colbourn, P.J. Slater, and L.K. Stewart, Locating-dominating sets in series parallel networks, Congr. Numer., 56 (1987), 135–162.

S.J. Esther and J.V. Vivik, The locating and locating domination of prism family graphs, Math. Stat., 12(3) (2024), 292–302.

M. Fazil, I. Javaid, M. Salman, and U. Ali, Locating-dominating sets in hypergraphs, Periodica Math. Hungar., 72(2) (2016), 224–234.

F. Foucaud, M.A. Henning, and C. Löwenstein, Locating-dominating sets in twin-free graphs, Discrete Appl. Math., 200 (2015), 52–58.

F. Foucaud, G.B. Mertzios, R. Naserasr, A. Parreau, and P. Valicov, Identification, location-domination and metric dimension on interval and permutation graphs. I. bounds, Theoret. Comput. Sci., 668 (2017), 43–58.

A.K.A. Gafur and S.W. Saputro, On locating-dominating set of regular graphs, J. Math., 2021 (2021), Article ID 8147514.

D. Garijo, A. González, and A. Márquez, The difference between the metric dimension and the determining number of a graph, Appl. Math. Comput., 249 (2014), 487–501.

M.A. Henning, and O.R. Oellermann, Metric-locating-dominating sets in graphs, Ars Comb., 73 (2004), 129–141.

C. Hernando, M. Mora, and I.M. Pelayo, Locating domination in bipartite graphs and their complements, Discrete Appl. Math., 263 (2019), 195–203.

L. Maro, A. Sanga, and M.E. Tuaty, Determination of the restrained domination number on vertex amalgamation and edge amalgamation of the path graph with the same order, Barekeng: Jurnal Ilmu Matematika dan Terapan, 16(2) (2022), 421–426.

M. Murtaza, M. Fazil, and I. Javaid, Locating-dominating sets of functigraphs, Theoret. Comput. Sci., 799 (2019), 115–123.

A.A. Pribadi and S.W. Saputro, On locating-dominating number of comb product graphs, Indones. J. Combin., 4(1) (2020), 27–33.

G. Rajasekar and K. Nagarajan, Algorithm for finding location domination number of a graph connected by a bridge, Int. J. Pure Appl. Math., 118(6) (2018), 313–321.

S.W. Saputro and I.R.A. As-Shidiq, On locating-dominating set of the Cartesian product of complete bipartite graphs and a path of order two, Jurnal Matematika UNAND, 14(3) (2025), 208–215.

P.J. Slater, Domination and location in acyclic graphs, Networks, 17 (1987), 55–64.

P.J. Slater, Dominating and reference sets in a graph, J. Math. Phys. Sci., 22 (1988), 445–455.

Y. Wahyuni, M.I. Utoyo, and Slamin, Domination number of vertex amalgamation of graphs, IOP Conf. Series: J. Phys: Conf. Series, 855 (2017), 012059.

Y. Yang, and X. Kong, The thickness of amalgamations of graphs, (2012), arXiv: 1201.6483v1.


Refbacks

  • There are currently no refbacks.


ISSN: 2338-2287

Creative Commons License
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.

View EJGTA Stats