On Factorable Extensions and Subgraphs of Prime Graphs
Joan Feigenbaum, Ramsey W. Haddad · SIAM Journal on Discrete Mathematics · 1989
Cartesian-factorable extensions and subgraphs of prime graphs are investigated. It is shown that minimal factorable extensions and maximal factorable subgraphs are not unique and that finding them is NP-hard even, in the case of minimal factorable extensions, if the prime graph in question is required to be a tree. Tight bounds on the density of a prime graph’s minimal factorable extension are derived. A dynamic programming algorithm is given for finding factorable extensions of certain types of trees.