In his Ph.D. thesis, Farber proved that every strongly chordal graph can be represented as intersection graph of subtrees of a weighted tree, and these subtrees are ``compatible''. Moreover, this is an equivalent characterization of strongly chordal graphs. To my knowledge, Farber never published his results in a conference or a journal, and the thesis is not available electronically. As a service to the community, I therefore reproduce the proof here. I then answer some questions that naturally arise from the proof. In particular, the sufficiency proof works by showing the existence of a simple vertex. I give here an alternate sufficiency proof that directly converts a set of compatible subtrees into a strong elimination order.
翻译:暂无翻译