Bounds of point-set domination number

Document Type : Special Issue for ICGCO-2022

Authors

1 University of Delhi

2 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

[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), 1–13.

[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.

[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. 

[6] P. Gupta and D. Jain, Bounds on 2-point set domination number of a graph, Discrete Math. Algorithms Appl. 10 (2018), no. 1, ID:1850012.

[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.

[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

Articles in Press, Accepted Manuscript
Available Online from 08 September 2022

Files

Share

How to cite

Statistics