A characterization of graphs with upper locating-domination number equal to $n-2$

Document Type : Research Paper

Authors

1 Laboratory, Department of Mathematics (LATSI), Faculty of Sciences, University of Blida 1, P.O.Box 270, Blida, Algeria

2 Laboratory of Mathematics and its Applications (LMA), Faculty of Technology, Medea University, Medea, Algeria

3 Laboratory of Mathematics and its Applications (LMA), Faculty of Sciences, Medea University, Medea, Algeria

Abstract

A set $D$ of vertices in a graph $G$ is called a dominating set of $G$ if every vertex in $V\left( G\right) \backslash D$ has at least one neighbor in $D$. A dominating set $D$ of $G$ is called a locating-dominating set of $G$ if every two vertices in $V\left( G\right) \backslash D$ have two distinct neighborhood sets. The upper locating-domination number $\Gamma_{L}(G)$ is the maximum cardinality of a minimal locating-dominating set of $G.$ In this paper, we characterize the graphs with $\Gamma_{L}\left( G\right) =n-2$.

Keywords

Main Subjects

References

[1] M. Blidia, M. Chellali, F. Maffray and A. Semri, Locating-domination and identifying codes in trees, Australas. J. Combin., 39 (2007) 219–232.
[2] M. Blidia, O. Favaron and R. Lounes, Locating-domination, 2-domination and independence in trees, Australas. J. Combin., 42 (2008) 309–316.
[3] M. Chellali, On locating and differentiating-total domination in trees, Discuss. Math. Graph Theory, 28 no. 3 (2008)
383–392.
[4] C. Berge, Graphs, Second revised edition of part 1 of the 1973 English version. North-Holland Mathematical Library, 6-1. North-Holland Publishing Co., Amsterdam, 1985.
[5] M. Chellali, M. Mimouni and P. J. Slater, On locating-domination in graphs, Discuss. Math. Graph Theory, 30 no. 2 (2010) 223–235.
[6] A. Finbow and B. L. Hartnell, On locating-dominating sets and well-covered graphs, Congr. Numer., 65 (1988) 191–200.
[7] F. Foucaud, M. A. Henning, Location-domination in line graphs, Discrete Math., 340 no. 1 (2017) 3140–3153.
[8] F. Foucaud and M. A. Henning, Location-domination and matching in cubic graphs, Discrete Math., 339 (2016) 1221–2231.
[9] F. Foucaud, M. A . Henning, C. Lowenstein and T. Sasse. Locating-dominating sets in twin-free graphs, Discrete Appl. Math., 200 (2016) 52–58.
[10] 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.
[11] J. Gimbel, B. van Gorden, M. Nicolescu, C. Umstead and N. Vaiana, Location with dominating sets, Congr. Numer., 151 (2001) 129–144.
[12] T. W. Haynes, M. A. Henning and J. Howard, Locating and total dominating sets in trees, Discrete Appl. Math., 154 (2006) 1293–1300.
[13] J. M. McCoy and M. A. Henning, Locating and paired dominating sets in graphs, Discrete Appl. Math., 157 (2009) 3268–3280.
[14] P. J. Slater, Domination and location in acyclic graphs, Networks, 17 (1987) 55–64.
[15] P. J. Slater, Dominating and reference sets in graphs, J. Math. Phys. Sci., 22 (1988) 445–455.
[16] Y. C. Zahao, E . F. Shan and R. Z. Gao, Upper locating-domination number of cycles, J. Math. Research and Exposition, 31 (2011) 757–760.

Files

History

  • Receive Date: 21 November 2023
  • Revise Date: 20 February 2025
  • Accept Date: 20 February 2025
  • Published Online: 01 March 2026

Share

How to cite

Statistics