On Minimal Geodetic Domination in Graphs

Hearty M. Nuenay; Ferdinand P. Jamil

Discussiones Mathematicae Graph Theory (2015)

  • Volume: 35, Issue: 3, page 403-418
  • ISSN: 2083-5892

Abstract

top
Let G be a connected graph. For two vertices u and v in G, a u-v geodesic is any shortest path joining u and v. The closed geodetic interval IG[u, v] consists of all vertices of G lying on any u-v geodesic. For S ⊆ V (G), S is a geodetic set in G if ∪u,v∈S IG[u, v] = V (G). Vertices u and v of G are neighbors if u and v are adjacent. The closed neighborhood NG[v] of vertex v consists of v and all neighbors of v. For S ⊆ V (G), S is a dominating set in G if ∪u∈S NG[u] = V (G). A geodetic dominating set in G is any geodetic set in G which is at the same time a dominating set in G. A geodetic dominating set in G is a minimal geodetic dominating set if it does not have a proper subset which is itself a geodetic dominating set in G. The maximum cardinality of a minimal geodetic dom- inating set in G is the upper geodetic domination number of G. This paper initiates the study of minimal geodetic dominating sets and upper geodetic domination numbers of connected graphs.

How to cite

top

Hearty M. Nuenay, and Ferdinand P. Jamil. "On Minimal Geodetic Domination in Graphs." Discussiones Mathematicae Graph Theory 35.3 (2015): 403-418. <http://eudml.org/doc/271213>.

@article{HeartyM2015,
abstract = {Let G be a connected graph. For two vertices u and v in G, a u-v geodesic is any shortest path joining u and v. The closed geodetic interval IG[u, v] consists of all vertices of G lying on any u-v geodesic. For S ⊆ V (G), S is a geodetic set in G if ∪u,v∈S IG[u, v] = V (G). Vertices u and v of G are neighbors if u and v are adjacent. The closed neighborhood NG[v] of vertex v consists of v and all neighbors of v. For S ⊆ V (G), S is a dominating set in G if ∪u∈S NG[u] = V (G). A geodetic dominating set in G is any geodetic set in G which is at the same time a dominating set in G. A geodetic dominating set in G is a minimal geodetic dominating set if it does not have a proper subset which is itself a geodetic dominating set in G. The maximum cardinality of a minimal geodetic dom- inating set in G is the upper geodetic domination number of G. This paper initiates the study of minimal geodetic dominating sets and upper geodetic domination numbers of connected graphs.},
author = {Hearty M. Nuenay, Ferdinand P. Jamil},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {minimal geodetic dominating set; upper geodetic domination number},
language = {eng},
number = {3},
pages = {403-418},
title = {On Minimal Geodetic Domination in Graphs},
url = {http://eudml.org/doc/271213},
volume = {35},
year = {2015},
}

TY - JOUR
AU - Hearty M. Nuenay
AU - Ferdinand P. Jamil
TI - On Minimal Geodetic Domination in Graphs
JO - Discussiones Mathematicae Graph Theory
PY - 2015
VL - 35
IS - 3
SP - 403
EP - 418
AB - Let G be a connected graph. For two vertices u and v in G, a u-v geodesic is any shortest path joining u and v. The closed geodetic interval IG[u, v] consists of all vertices of G lying on any u-v geodesic. For S ⊆ V (G), S is a geodetic set in G if ∪u,v∈S IG[u, v] = V (G). Vertices u and v of G are neighbors if u and v are adjacent. The closed neighborhood NG[v] of vertex v consists of v and all neighbors of v. For S ⊆ V (G), S is a dominating set in G if ∪u∈S NG[u] = V (G). A geodetic dominating set in G is any geodetic set in G which is at the same time a dominating set in G. A geodetic dominating set in G is a minimal geodetic dominating set if it does not have a proper subset which is itself a geodetic dominating set in G. The maximum cardinality of a minimal geodetic dom- inating set in G is the upper geodetic domination number of G. This paper initiates the study of minimal geodetic dominating sets and upper geodetic domination numbers of connected graphs.
LA - eng
KW - minimal geodetic dominating set; upper geodetic domination number
UR - http://eudml.org/doc/271213
ER -

References

top
  1. [1] S. Canoy Jr. and G. Cagaanan, On the geodesic and hull numbers of graphs, Congr. Numer. 161 (2003) 97-104. Zbl1053.05038
  2. [2] S. Canoy Jr. and G. Cagaanan, On the geodetic covers and geodetic bases of the composition G[Km], Ars Combin. 79 (2006) 33-45. 
  3. [3] G. Chartrand, F. Harary and P. Zhang, Geodetics sets in graphs, Discuss. Math. Graph Theory 20 (2000) 129-138. doi:10.7151/dmgt.1112[Crossref] 
  4. [4] G. Chartrand, F. Harary and P. Zhang, On the geodetic number of a graph, Networks 39 (2002) 1-6. doi:10.1002/net.10007[Crossref] Zbl0987.05047
  5. [5] I. Aniversario, F. Jamil and S. Canoy Jr., The closed geodetic numbers of graphs, Util. Math. 74 (2007) 3-18. Zbl1176.05040
  6. [6] S. Canoy Jr., G. Cagaanan and S. Gervacio, Convexity, geodetic and hull numbers of the join of graphs, Util. Math. 71 (2007) 143-159. Zbl1109.05040
  7. [7] S. Canoy Jr. and I.J. Garces, Convex sets under some graph operations, Graphs Combin. 18 (2002) 787-793. doi:0.1007/s003730200065 Zbl1009.05054
  8. [8] H. Escuardo, R. Gera, A. Hansberg, N. Jafari Rad and L. Volkmann, Geodetic domination in graphs, J. Combin. Math. Combin. Comput. 77 (2011) 89-101. Zbl1238.05072
  9. [9] T. Haynes, S.T. Hedetniemi and P. Slater, Fundamentals of Domination in Graphs (Marcel Dekker, Inc. New York, 1998). Zbl0890.05002
  10. [10] T. Haynes, S.M. Hedetniemi, S.T. Hedetniemi and M. Henning, Domination in graphs applied to electrical power networks, SIAM J. Discrete Math. 15 (2000) 519-529. doi:10.1137/S0895480100375831[Crossref] 
  11. [11] F. Buckley and F. Harary, Distance in Graphs (Redwood City, CA: Addison-Wesley, 1990). Zbl0688.05017
  12. [12] M. Lema´nska, Weakly convex and convex domination numbers, Opuscula Math. 24 (2004)) 181-188. 
  13. [13] J. Bondy and G. Fan, A sufficient condition for dominating cycles, Discrete Math. 67 (1987) 205-208. doi:10.1016/0012-365X(87)90029-X[Crossref] 
  14. [14] E. Cockayne and S.T. Hedetniemi, Towards a theory of domination in graphs, Net- works 7 (1977) 247-261. doi:10.1002/net.3230070305[Crossref] 
  15. [15] H. Walikar, B. Acharya and E. Samathkumar, Recent Developments in the Theory of Domination in Graphs (Allahabad, 1979). 
  16. [16] T.L. Tacbobo, F.P.Jamil and S. Canoy Jr., Monophonic and geodetic domination in the join, corona and composition of graphs, Ars Combin. 112 (2013) 13-32. Zbl1313.05287

NotesEmbed ?

top

You must be logged in to post comments.