In general, the minimum connected dominating set (MCDS) of a graph is not unique.

Q1: Is there a conventional name for the set of vertices which are never part of any MCDS?

Q2: Has anyone ever encountered mention of this set in the literature? My search has turned up nothing, but I'm a non-mathematician who's new to graph theory.

Leaves are obviously in this (nameless?) set, but there are others, as well. Consider, for example, the paw or 3-pan graph, which consists of 4 vertices and 4 edges, and is obtained by joining a leaf to $C_3$. The MCDS is unique in this case, and it's a single vertex; thus, none of the other three vertices are ever part of a MCDS for this graph, yet only one of them is a leaf vertex.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.