On the edge geodetic and edge geodetic domination numbers of a graph

Document Type : Original paper

Author

University of Architecture, Civil Đ•ngineering and Geodesy; Department of Mathematics

Abstract

In this paper, we study both concepts of geodetic dominating and edge geodetic dominating sets and derive some tight upper bounds on the edge geodetic and the edge geodetic domination numbers. We also obtain attainable upper bounds on the maximum number of elements in a partition of a vertex set of a connected graph into geodetic sets, edge geodetic sets, geodetic dominating sets and edge geodetic dominating sets, respectively.

Keywords

Main Subjects

References

[1] D.W. Bange, A.E Barkauskas, and P.J. Slater, Efficient dominating sets in graphs, Applications of Discrete Mathematics, SIAM - Philadelphia, 1988, pp. 189–199.
[2] J. Cao, B. Wu, and M. Shi, The geodetic number of cm × cn, International Conference on Management and Service Science, Wuhan, 9 2009, pp. 1–3.
[3] E.J. Cockayne and S.T. Hedetniemi, Towards a theory of domination in graphs, Networks 7 (1977), 247–261.
[4] M.C. Dourado, F. Protti, D. Rautenbach, and J.L. Szwarcfiter, Some remarks on the geodetic number of a graph, Discrete Math. 310 (2010), 832–837.
[5] 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.
[6] J.F. Fink, M.S. Jacobson, L.F. Kinch, and J. Roberts, On graphs having domination number half their order, Period. Math. Hungar. 16 (1985), 287–293.
[7] T. Gallai, Uber extreme punkt- und kantenmengen, Ann. Univ. Sci. Budapest, Eotvos Sect. Math. 2 (1959), 133–138.
[8] A. Hansberg and L. Volkmann, On the geodetic and geodetic domination numbers of a graph, Discrete Math. 310 (2010), 2140–2146.
[9] F. Harary, E. Loukakis, and C. Tsouros, The geodetic number of a graph, Mathl. Comput. Modelling 17 (1993), no. 11, 89–95.
[10] T.W. Haynes, S.T. Hedetniemi, and P.J. Slater, Fundamentals of Domination in Graphs, Marcel Dekker - New York, 1998.
[11] S. Klaviar and N. Seifter, Dominating cartesian products of cycles, Discrete Appl. Math. 59 (1995), 129–136.
[12] O. Ore, Theory of graphs, American Mathematical Society - Providence, 1967. 
[13] C. Payan and N.H. Xuong, Domination-balanced graphs, J. Graph Theory 6 (1982), 23–32.
[14] B. Randerath and L. Volkmann, Characterization of graphs with equal domination and covering number, Discrete Math. 191 (1998), 159–169.
[15] V. Samodivkin, Common extremal graphs for three inequalities involving domination parameters, Trans. Comb. 6 (2017), no. 3, 1–9.
[16] A.P. Santhakumaran and J. John, Edge geodetic number of a graph, J. Discrete Math. Sci. Cryptogr. 10 (2007), no. 3, 415–432.
[17] A.P. Santhakumaran and J. John, The upper edge geodetic number and the forcing edge geodetic number of a graph, Opuscula Math. 29 (2009), no. 4, 427–441.
[18] A.P. Santhakumaran and S.V. Ullas Chandran, Comment on ”edge geodetic covers in graphs”, Proyecciones Journal of Mathematics 34 (2015), no. 4, 343–350.
[19] P. Arul Paul Sudhahar, A. Ajitha, and A. Subramanian, Edge geodetic domination number of a graph, Int. J. Math. Appl. 4 (2016), no. 3-B, 45–50.
 
Communications in Combinatorics and Optimization
Volume 5, Issue 1
June 2020
Pages 41-54

Files

Share

How to cite

Statistics