On the upper geodetic global domination number of a graph
DOI:
https://doi.org/10.22199/issn.0717-6279-2020-06-0097Keywords:
Geodetic set, Dominating set, Geodetic domination, Geodetic global domination, Upper geodetic global domination numberAbstract
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.
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
How to Cite
Issue
Section
Copyright (c) 2020 X. Lenin Xaviour, S. Robinson Chellathurai
This work is licensed under a Creative Commons Attribution 4.0 International License.
-
Attribution — You must give appropriate credit, provide a link to the license, and indicate if changes were made. You may do so in any reasonable manner, but not in any way that suggests the licensor endorses you or your use.
- No additional restrictions — You may not apply legal terms or technological measures that legally restrict others from doing anything the license permits.