A note on connected dominating sets of distance-hereditary graphs

A vertex subset of a graph is a dominating set if every vertex of the graph belongs to the set or has a neighbor in it. A connected dominating set is a dominating set such that the induced subgraph of the set is a connected graph. A graph is called distance-hereditary if every induced path is a shortest path.In this note, we give a complete description of the (inclusionwise) minimal connected dominating sets of connected distance-hereditary graphs: if GG is a connected distance-hereditary graph that has a dominating vertex, any minimal connected dominating set is a single vertex or a pair of two adjacent vertices. If GG does not have a dominating vertex, the subgraphs induced by any two minimal connected dominating sets are isomorphic. In particular, any inclusionwise minimal connected dominating set of a connected distance-hereditary graph without dominating vertex has minimal size. In other words, connected distance-hereditary graphs without dominating vertex are connected well-dominated.This answers a question of Chen et al. [X. Chen, A.A. McRae, L. Sun, Tree domination in graphs, Ars Combinatoria 73 (2004), pp. 193–203.] asking for non-trivial graph classes where the minimal size of a connected dominating set inducing a tree can be computed efficiently.Furthermore, we show that if GG is a distance-hereditary graph that has a minimal connected dominating set XX of size at least 2, then for any connected induced subgraph HH it holds that the subgraph induced by any minimal connected dominating set of HH is isomorphic to an induced subgraph of G[X]G[X].