Menu
In this note, we consider finite, undirected, and simple graphs. A subset \(D\) of the vertex set of a graph \(G\) is a dominating set if each vertex of \(G\) is either in \(D\) or adjacent to some vertex of \(D\). A dominating set of minimum cardinality is called a minimum dominating set
A vertex \(v\) of a graph \(G\) is called a cut-vertex of G if \(G – v\) has more components than \(G\). A block of a graph is a maximal connected subgraph having no cut-vertex.
A block-cactus graph is a graph whose blocks are either complete graphs or cycles, and we speak of a cactus if the complete graphs consist of only one edge.
In our main theorem, we shall show that the minimum dominating set problem of an arbitrary graph can be reduced to its blocks. This theorem provides a linear-time algorithm for determining a minimum dominating set in a block-cactus graph, and thus, it can be seen as a supplement to a linear-time algorithm for finding a minimum dominating set in a cactus, presented by S.T. Hedetniemi, R.C. Laskar, and J. Pfaff in 1986.