The geodetic domination number of comb product graphs

Dimas Agus Fahrudin, Suhadi Wido Saputro


A subset S of vertices in graph G is called a geodetic set if every vertex in V(G) \ S lies on a shortest path between two vertices in S. A subset S of vertices in G is called a dominating set if every vertex in V(G) \  S is adjacent to a vertex in S. The set S is called a geodetic dominating set if S is both geodetic and dominating sets. The geodetic domination number of G, denoted by γg(G), is the minimum cardinality of geodetic domination sets in G. The comb product of connected graphs G and H at vertex o ∈ V(H), denoted by  G ∇o H, is a graph obtained by taking one copy of G and |V(G)| copies of H and identifying the ith copy of H at the vertex o to the ith vertex of G. In this paper, we determine an exact value of γg(G ∇o H) for any connected graphs G and H.


comb product, domination number, geodetic domination number, geodetic number

Full Text:




M. Azari and A. Iranmanesh, Chemical graphs constructed from rooted product and their Zagreb indices, MATCH Commun. Math. Comput. Chem. 70 (2013), 901–919.

M. Blidia, M. Chellali, F. Maffray, J. Moncel, and A. Semri, Locating-domination and identifying codes in trees, Australas. J. Combin. 39 (2007), 219-232.

B. Bresar, S. Klavzar, and A.T. Horvat, On the geodetic number and related metrics sets in Cartesian product graphs, Discrete Math. 308 (2008), 5555–5561.

L.F. Casinillo, A note on Fibonacci and Lucas number of domination in path, Electron. J. Graph Theory Appl. 6 (2) (2018), 317–325.

G. Chartrand, F. Harary, and P. Zhang, On the geodetic number of a graph, Networks 39 (2002), 1–6.

M. Chellali, N.J. Rad, S.J. Seo, and P.J. Slater, On Open Neighborhood Locating-dominating in Graphs, Electron. J. Graph Theory Appl. 2 (2014), 87-98.

S.R. Chellathurai and S.P. Vijaya, Geodetic domination in the corona and join of graphs, J. Discrete Math. Sci. Cryptogr. 17 (1) (2014), 81–90.

S.R. Chellathurai and S.P. Vijaya, The geodetic domination number for the product of graphs, Trans. Combin. 3 (4) (2014), 19–30.

E.J. Cockayne, P.A. Dreyer Jr., S.M. Hedetniemi, and S.T. Hedetniemi, Roman domination in graphs, Discrete Math. 278 (2004), 11–22.

E.J. Cockayne and S.T. Hedetniemi, Towards a theory of domination in graphs, Networks 7 (3) (1977), 247–261.

Darmaji and R. Alfarisi, On the partition dimension of comb of path and complete graph, AIP Conf. Proc. 1867 (2017), 020038.

H. Escuadro, R. Gera, A. Hansberg, N. Jafari Rad, and L. Volkman, Geodetic domination in graphs, J. Combin. Math. Combin. Comput. 77 (2011), 89–101.

X. Fu, Y. Yang, and B. Jiang, Roman domination in regular graphs, Discrete Math. 309 (2009), 1528–1537.

W. Goddard and M.A. Henning, Independent domination in graphs: A survey and recent results, Discrete Math. 313 (2013), 839–854.


  • There are currently no refbacks.

ISSN: 2338-2287

Creative Commons License
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.

View EJGTA Stats