Characterization of cactus-expandable digraphs via doubly bidirectionally connected pairs

Abstract

Azuma et al.\ showed that a strongly connected digraph without a doubly bidirectionally connected pair is cactus-expandable. We prove the converse: if a digraph has a doubly bidirectionally connected pair, then no expansion of it is a cactus digraph. Combined with the theorem of Azuma et al., this yields a characterization of strongly connected cactus-expandable digraphs.

7 pages, 2 figures