The geodetic domination number for the product of graphs

Document Type : Research Paper


1 Scott Christian College

2 University College of Engineering Nagercoil


A subset $S$ of vertices in a graph $G$ is called a geodetic set if every vertex not in $S$ lies on a shortest path between two vertices from $S$‎. ‎A subset $D$ of vertices in $G$ is called dominating set if every vertex not in $D$ has at least one neighbor in $D$‎. ‎A geodetic dominating set $S$ is both a geodetic and a dominating set‎. ‎The geodetic (domination‎, ‎geodetic domination) number $g(G) (\gamma(G),\gamma_g(G))$ of $G$ is the minimum cardinality among all geodetic (dominating‎, ‎geodetic dominating) sets in $G$‎. ‎In this paper‎, ‎we show that if a triangle free graph $G$ has minimum degree at least 2 and $g(G) = 2$‎, ‎then $\gamma _g(G) = \gamma(G)$‎. ‎It is shown‎, ‎for every nontrivial connected graph $G$ with $\gamma(G) = 2$ and $diam(G) > 3$‎, ‎that $\gamma_g(G) > g(G)$‎. ‎The lower bound for the geodetic domination number of Cartesian product graphs is proved‎. ‎Geodetic domination number of product of cycles (paths) are determined‎. In this work‎, ‎we also determine some bounds and exact values of the geodetic domination number of strong product of graphs‎.


Main Subjects

B. Bresar, S. Klavzar and A. T. Horvat (2008). On the geo detic numb er and related metric sets in Cartesian pro duct graphs. Discrete Math.. 308, 5555-5561 F. Buckley and F. Harary (1990). Distance in Graphs. Addison-Wesley Publishing Company, Redwo o d City, CA,. J. Caceres, C. Hernando, M. Mora and I. M. Pelayo (2010). On the geo detic and hull numb ers in strong pro duct graphs. Comput. Math. Appl.. 60, 3020-3031 H. Escuadro, R. Gera, A. Hansb erg, N. Jafari Rad and L. Volkmann (2011). Geo detic Domination in Graphs. J. Combin. Math. Combin. Comput.. 77, 89-101 G. Chartrand, F. Harary and P. Zhang (2002). On the Geo detic Numb er of a Graph. Networks. 39, 1-6 A. Hansb erg and L. Volkmann (2010). On the geo detic and geo detic domination numb ers of a graph. Discrete Math.. 310, 2140-2146 F. Harary, E. Loukakis and C. Tsouros (1993). The geo detic numb er of a graph. Math. Comput. Model ling. 17 (11), 89-95 T. W. Haynes, S. T. Hedetniemi and P. J. Slater (1998). Fundamentals of domination in graphs. Marcel Dekker, Inc, New York. 208 M. S. Jacobson and L. F. Kinch (1984). On the domination numb er of pro ducts of graphs I. Ars Combin.. 18, 33-44 J. Cao, B. Wu and M. Shi (2009). The geo detic Numb er of C m* C n. IEEE. S. Klavzar and N. Seifter (1995). Dominating Cartesian pro ducts of cycles. Discrete Appl. Math.. 59, 129-136 A. P. Santhakumaran and S. V. Ullas Chandran (2010). The geo detic numb er of strong pro duct graphs. Discuss. Math. Graph Theory. 30 (4), 687-700 T. Jiang, I. Pelayo and D. Pritikin (2004). Geo desic convexity and Cartesian pro ducts in graphs. I. G. Yero and J. A. Ro driguez-velazquez Domination and Roman domination in graphs pro duct. Manuscript. I. G. Yero and J. A. Ro driguez-velazquez (2013). Roman domination in cartesian pro duct graphs and strong product graphs. Applicable Analysis and Discrete Mathematics. 7, 262-274
Volume 3, Issue 4 - Serial Number 4
December 2014
Pages 19-30
  • Receive Date: 06 March 2014
  • Revise Date: 20 June 2014
  • Accept Date: 27 June 2014
  • Published Online: 01 December 2014