<i>P</i>₄‐Reducible Graphs—Class of Uniquely Tree‐Representable Graphs

Abstract

We introduce and characterize a new class of graphs which has a unique tree representation, and which strictly contains the well‐known class of cographs. We define three graph operations and show that all the graphs in our class can be constructed from single‐vertex graphs by a finite sequence of these operations. Finally, we show that a number of computational problems, including the four classical optimization problems, can be solved efficiently for this new class of graphs.