Connected geodomination in graphs
Doost Ali Mojdeh, Nader Jafari Rad · Journal of Discrete Mathematical Sciences and Cryptography · 2006
A pair x, y of vertices in a nontrivial connected graph G is said to geodominate a vertex v of G if either v∈{x, y} or v lies in an x–y geodesic of G. A set S of vertices of G is a geodominating set if every vertex of G is geodominated by some pair of vertices of S. A vertex of G is link-complete if the subgraph induced by its neighborhood is complete. A pair x, y of vertices in G is said to openly geodominate a vertex v of G if v≠x, y and v is geodominated by x and y. A set S is an open geodominating set of G if for each vertex v, either (1) v is link-complete and v∈S or (2) v is openly geodominated by some pair of vertices of S. A connected geodominating set is a geodominating set which is connected. The cardinality of a minimum connected geodominating set in G is its connected geodomination number g c (G). For a minimum connected geodominating set S of G, a subset T⊆S is said to be a forcing set if S is the unique connected geodominating set containing T. The forcing connected geodomination number f(G,g c (G)) is the minimum size of a forcing connected geodominating set among the forcing connected geodominating sets of G. We study (open) connected geodomination number and forcing connected geodomination number in a graph G.