On the upper geodetic global domination number of a graph

Authors

DOI:

https://doi.org/10.22199/issn.0717-6279-2020-06-0097

Keywords:

Geodetic set, Dominating set, Geodetic domination, Geodetic global domination, Upper geodetic global domination number

Abstract

A set S of vertices in a connected graph G = (V, E) is called a geodetic set if every vertex not in S lies on a shortest path between two vertices from S. A set D of vertices in G is called a dominating set of G if every vertex not in D has at least one neighbor in D. A set D is called a global dominating set in G if S is a dominating set of both G and Ḡ. A set S is called a geodetic global dominating set of G if S is both geodetic and global dominating set of G. A geodetic global dominating set S in G is called a minimal geodetic global dominating set if no proper subset of S is itself a geodetic global dominating set in G. The maximum cardinality of a minimal geodetic global dominating set in G is the upper geodetic global domination number Ῡg+(G) of G. In this paper, the upper geodetic global domination number of certain connected graphs are determined and some of the general properties are studied. It is proved that for all positive integers a, b, p where 3 ≤ a ≤ b < p, there exists a connected graph G such that Ῡg(G) = a, Ῡg+(G) = b and |V (G)| = p.

Author Biographies

X. Lenin Xaviour, Manonmaniam Sundaranar University.

Scott Christian College, Dept. of Mathematics.

S. Robinson Chellathurai, Manonmaniam Sundaranar University.

Scott Christian College, Dept. of Mathematics.

References

F. Buckley and F. Harary, Distance in graphs. Redwood City, CA: Addison-Wesley, 1990.

G. Chartrand, F. Harary, and P.Chang, “On the geodetic number of a graph”, Networks, vol. 39, no.1, pp. 1-6, Jan. 2002, doi: 10.1002/net.10007

W. J. Desormeaux, P. E. Gibson, and T. W. Haynes, “Bounds on the global domination number”, Quaestiones mathematicae, vol. 38, no. 4, pp. 563-572, Jun. 2015, doi: 10.2989/16073606.2014.981728.

H. Escuadro, R. Gera, A. Hansberg, N. Jafari Rad, and L. Volkmann, “Geodetic domination in graphs”, Journal of combinatorial mathematics and combinatorial computing, vol. 77, pp. 88-101, May 2011. [On line]. Available: https://bit.ly/3p6DuWZ

T. W. Haynes, P. J. Slater, and S. T. Hedetniemi, Fundamentals of domination in graphs. Boca Raton, CA: CRC Press, 1998, doi: 10.1201/9781482246582

H. M. Nuenay and F. P. Jamil, “On minimal geodetic domination in graphs”, Discussiones mathematicae graph theory, vol. 35, no. 3, pp. 403-418, Jul. 2015, doi: 10.7151/dmgt.1803

S. R. Chellathurai and L. Xaviour, “Geodetic global domination in graphs”, International journal of mathematical archive, vol. 9, no. 4, pp. 29-36, 2018. [On line]. Available: https://bit.ly/38mtIKv

E. Sampath Kumar, “The global domination number of a graph”, Journal of mathematical and physical sciences, vol. 23, no. 5, pp. 377-385, 1989. [On line]. Available: https://bit.ly/3kbwpR6

D. B. West, Introduction to graph theory, 2nd ed. Upper Saddle River, NJ: Prentice-Hall, 2001.

Published

2020-11-12

How to Cite

[1]
X. L. Xaviour and S. R. Chellathurai, “On the upper geodetic global domination number of a graph”, Proyecciones (Antofagasta, On line), vol. 39, no. 6, pp. 1627-1646, Nov. 2020.

Issue

Section

Artículos

Most read articles by the same author(s)