کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4647897 | 1342382 | 2012 | 10 صفحه PDF | دانلود رایگان |
![عکس صفحه اول مقاله: Finding intersection models: From chordal to Helly circular-arc graphs Finding intersection models: From chordal to Helly circular-arc graphs](/preview/png/4647897.png)
Every chordal graph G admits a representation as the intersection graph of a family of subtrees of a tree. A classic way of finding such an intersection model is to look for a maximum spanning tree of the valuated clique graph of G. Similar techniques have been applied to find intersection models of chordal graph subclasses as interval graphs and path graphs. In this work, we extend those methods to be applied beyond chordal graphs: we prove that a graph G can be represented as the intersection of a Helly separating family of graphs belonging to a given class if and only if there exists a spanning subgraph of the clique graph of G satisfying a particular condition. Moreover, such a spanning subgraph is characterized by its weight in the valuated clique graph of G. The specific case of Helly circular-arc graphs is treated. We show that the canonical intersection models of those graphs correspond to the maximum spanning cycles of the valuated clique graph.
Journal: Discrete Mathematics - Volume 312, Issue 6, 28 March 2012, Pages 1148–1157