On Minimal Geodetic Domination in Graphs

• Autorzy: Hearty M. Nuenay , Ferdinand P. Jamil
• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

minimal geodetic dominating set; upper geodetic domination number

• Wydawca: De Gruyter Open
• Czasopismo: Discussiones Mathematicae Graph Theory
• Rocznik: 2015
• Tom: 35
• Numer: 3
• Strony: 403-418

Daty

wydano

2015-08-01

otrzymano

2013-12-28

poprawiono

2014-06-25

zaakceptowano

2014-08-01

online

2015-07-29

Twórcy

autor

Hearty M. Nuenay

• Department of Mathematics and Statistics MSU-Iligan Institute of Technology Iligan City, Philippines

autor

Ferdinand P. Jamil

• Department of Mathematics and Statistics MSU-Iligan Institute of Technology Iligan City, Philippines

Bibliografia

• [1] S. Canoy Jr. and G. Cagaanan, On the geodesic and hull numbers of graphs, Congr. Numer. 161 (2003) 97-104.
• [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] 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] 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]
• [5] I. Aniversario, F. Jamil and S. Canoy Jr., The closed geodetic numbers of graphs, Util. Math. 74 (2007) 3-18.
• [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.
• [7] S. Canoy Jr. and I.J. Garces, Convex sets under some graph operations, Graphs Combin. 18 (2002) 787-793. doi:0.1007/s003730200065
• [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.
• [9] T. Haynes, S.T. Hedetniemi and P. Slater, Fundamentals of Domination in Graphs (Marcel Dekker, Inc. New York, 1998).
• [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] F. Buckley and F. Harary, Distance in Graphs (Redwood City, CA: Addison-Wesley, 1990).
• [12] M. Lema´nska, Weakly convex and convex domination numbers, Opuscula Math. 24 (2004)) 181-188.
• [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] 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] H. Walikar, B. Acharya and E. Samathkumar, Recent Developments in the Theory of Domination in Graphs (Allahabad, 1979).
• [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.

Identyfikatory

DOI

10.7151/dmgt.1803