Graphs with convex domination number close to their order
Joanna Cyman, Magdalena Lemańska, Joanna Raczek · Discussiones Mathematicae Graph Theory · 2006
For a connected graph G = (V,E), a set D ⊆ V (G) is a dominating set of G if every vertex in V (G)−D has at least one neighbour in D. The distance dG(u, v) between two vertices u and v is the length of a shortest (u − v) path in G. An (u − v) path of length dG(u, v) is called an (u − v)-geodesic. A set X ⊆ V (G) is convex in G if vertices from all (a − b)-geodesics belong to X for any two vertices a, b ∈ X. A set X is a convex dominating set if it is convex and dominating. The convex domination number γcon(G) of a graph G is the minimum cardinality of a convex dominating set in G. Graphs with the convex domina-tion number close to their order are studied. The convex domination number of a Cartesian product of graphs is also considered.