YLL討論網

A block in a graph G is a maximal biconnected component. G is a block graph if every
block of G is a clique. G is a cactus graph if every block of G is either a cycle or an
edge. G is a block-cactus graph if every block of G is either a clique or a cycle. Answer
the following questions.
(1) How to recognize a block-cactus graph?
(2) Are block, cactus, and block-cactus graphs perfect? Note that a graph is perfect
if its chromatic number equals to its maximum clique size.
(3) Propose an algorithm to find a minimum dominating set on a block-cactus
graph.