Bounds of point-set domination number

Document Type : Short notes

Authors

1 Department of Mathematics, University of Delhi

2 Department of Mathematics, Deshbandhu College, University of Delhi

3 Department of Mathematics, Sri Venkateswara College, University of Delhi

Abstract

A subset $D$ of the vertex set $V(G)$ in a graph $G$ is a point-set dominating set (or, in short, psd-set) of $G$ if for every set $S\subseteq V- D$, there exists a vertex $v\in D$ such that the induced subgraph $\langle S\cup \{v\}\rangle$ is connected.  The minimum cardinality of a psd-set of $G$ is called the point-set domination number of $G$. In this paper, we establish two sharp lower bounds for point-set domination number of a graph in terms of its diameter and girth. We characterize graphs for which lower bound of point set domination number is attained in terms of its diameter. We also establish an upper bound and give some classes of graphs which attains the upper bound of point set domination number.

Keywords

Main Subjects

References

[1] B.D. Acharya and P. Gupta, On point-set domination in graphs IV: Separable graphs with unique minimum psd-sets, Discrete Math. 195 (1999), no. 1-3, 1–13.
https://doi.org/10.1016/S0012-365X(98)00160-5
[2] G. Chartrand and L. Lesniak, Graphs & Digraphs, fourth ed., Chapman & Hall/CRC, Boca Raton, FL, 2005.
[3] B. Gayathri and S. Kaspar, Point set tree domination in graphs, Int. J. Math. Comput. Sci. 2 (2007), no. 4, 377–380.
[4] P. Gupta and D. Jain, Global 2-point set domination number of a graph, International Conference on Graph Theory and its Applications, Electron. Notes Discrete Math., vol. 53, Elsevier Sci. B. V., Amsterdam, 2016, pp. 213–224.
https://doi.org/10.1016/j.endm.2016.05.019
[5] P. Gupta and D. Jain, Independent 2-point set domination in graphs, Theoretical Computer Science and Discrete Mathematics, Lecture Notes in Comput. Sci., vol. 10398, Springer, Cham, 2017, pp. 281–288.
https://doi.org/10.1007/978-3-319-64419-6_36
[6] P. Gupta and D. Jain, Bounds on 2-point set domination number of a graph, Discrete Math. Algorithms Appl. 10 (2018), no. 1, Article ID: 1850012.
https://doi.org/10.1142/S179383091850012X
[7] P. Gupta, R. Singh, and S. Arumugam, Characterizing minimal point set dominating sets, AKCE Int. J. Graphs Comb. 13 (2016), no. 3, 283–289.
https://doi.org/10.1016/j.akcej.2016.07.003
[8] F. Harary, Graph Theory, Addison-Wesley Publishing Co., Reading, Mass.-Menlo Park, Calif.-London, 1969.
[9] T.W. Haynes, S.T. Hedetniemi, and P.J. Slater, Domination in Graphs-Advanced Topics, Marcel Dekker, Inc., New York, 1998.
[10] T.W. Haynes, S.T. Hedetniemi, and P.J. Slater, Fundamentals of Domination in Graphs, Marcel Dekker, Inc., New York,
1998.
[11] L. PushpaLatha, The global point-set domination number of a graph, Indian J. Pure Appl. Math. 28 (1997), no. 1, 47–51.
[12] E. Sampathkumar and L. Pushpa Latha, Point-set domination number of a graph, Indian J. Pure Appl. Math. 24 (1993), no. 4, 225–229.
Communications in Combinatorics and Optimization
Volume 9, Issue 1
March 2024
Pages 79-87

Files

Share

How to cite

Statistics