کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
419533 | 683834 | 2010 | 9 صفحه PDF | دانلود رایگان |
![عکس صفحه اول مقاله: The clique operator on circular-arc graphs The clique operator on circular-arc graphs](/preview/png/419533.png)
A circular-arc graph GG is the intersection graph of a collection of arcs on the circle and such a collection is called a model of GG. Say that the model is proper when no arc of the collection contains another one, it is Helly when the arcs satisfy the Helly Property, while the model is proper Helly when it is simultaneously proper and Helly. A graph admitting a Helly (resp. proper Helly) model is called a Helly (resp. proper Helly) circular-arc graph. The clique graph K(G)K(G) of a graph GG is the intersection graph of its cliques. The iterated clique graph Ki(G)Ki(G) of GG is defined by K0(G)=GK0(G)=G and Ki+1(G)=K(Ki(G))Ki+1(G)=K(Ki(G)). In this paper, we consider two problems on clique graphs of circular-arc graphs. The first is to characterize clique graphs of Helly circular-arc graphs and proper Helly circular-arc graphs. The second is to characterize the graph to which a general circular-arc graph KK-converges, if it is KK-convergent. We propose complete solutions to both problems, extending the partial results known so far. The methods lead to linear time recognition algorithms, for both problems.
Journal: Discrete Applied Mathematics - Volume 158, Issue 12, 28 June 2010, Pages 1259–1267