A subset D of the vertex set  of a graph G is said to be a dominating set if every vertex not in D is adjacent to at least one vertex in D. In this paper, we define some new concepts known as median -set of a graph and a -set with minimum status. For a dominating set D of a graph G, define the status of D as   where  denotes the sum of the distances from v to each vertex in D. Let  be a -set of  Let D be a -set such that  A -set D with minimum status  is known as a median -set and this  is known as the dominating status of the graph G. In this paper, the concepts of a minimum dominating set with minimum status (median -set) and dominating status in a graph are defined. The median -set and dominating status of some classes of graphs are determined. Also, an algorithm for finding dominating status of a graph using distance matrix is given.

domination, dominating status, minimum dominating sets.

Received: June 11, 2022; Revised: July 20, 2022; Accepted: July 28, 2022 Published: August 23, 2022

How to cite this article: M. Bhanumathi and R. Niroja, Minimum dominating sets with minimum status in graphs, Advances and Applications in Discrete Mathematics 33 (2022), 73-96. http://dx.doi.org/10.17654/0974165822038

This Open Access Article is Licensed under Creative Commons Attribution 4.0 International License

References:

[1] F. Buckley and F. Harary, Distance in Graphs, Addison-Wesley, Publishing Company, 1990.
[2] E. J. Cockayne and S. T. Hedetniemi, Towards a theory of domination in graphs, Networks 7 (1977), 247-261.
[3] R. C. Entringer, D. E. Jackson and D. A. Snyder, Distance in graphs, Czech Math. J. 26(2) (1976), 283-296.
[4] F. Harary, Graph Theory, Addition-Wesley Publishing Company Reading, Mass, 1972.
[5] T. W. Haynes, S. T. Hedetniemi and P. J. Slater, Fundamentals of Domination in Graphs, Marcel Dekker, New York, 1998.
[6] O. Ore, Theory of graphs, Amer. Math. Soc. Transl. 38 (1962), 206-212.
[7] H. B. Walikar, V. S. Shigehalli and H. S. Ramane, Bounds on the Wiener number of a graph, Communications in Mathematical and in Computer Chemistry 50 (2004), 117-132.
[8] H. Wiener, Structural determination of paraffin boiling points, Journal of the American Chemical Society 69 (1947), 17-20.
[9] Bohdan Zelinka, Medians and peripherians of trees, Arch. Math. (Brno) 4 (1968),
87-95.