Paper Info
Title
The clique operator on circular-arc graphs
Abstract
A circular-arc graphG is the intersection graph of a collection of arcs on the circle and such a collection is called a model of G. 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 graphK(G) of a graph G is the intersection graph of its cliques. The iterated clique graphK^i(G) of G is defined by K^0(G)=G and K^i^+^1(G)=K(K^i(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 K-converges, if it is K-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.
Year
DOI
Venue
2010
10.1016/j.dam.2009.01.019
Discrete Applied Mathematics
Keywords
Field
DocType
clique graphs,proper helly circular-arc graphs,helly property,helly circular-arc graphs,algorithms,k-behaviour,helly circular-arc graph,proper helly circular-arc graph,circular-arc graphg,circular-arc graph,k -behavior,graph g,proper helly,clique operator,general circular-arc graph k-converges,clique graph,intersection graph,k,satisfiability,linear time
Block graph,Discrete mathematics,Combinatorics,Helly's theorem,Clique graph,Chordal graph,Clique-sum,Cograph,Treewidth,Mathematics,Split graph
Journal
Volume
Issue
ISSN
158
12
Discrete Applied Mathematics
Citations 
PageRank 
References 
10
0.52
22
Authors
3
Name
Order
Citations
PageRank
Min Chih Lin125921.22
Francisco J. Soulignac210110.56
Jayme L. Szwarcfiter354645.97