Paper Info
Title
Clique graphs of Helly circular arc graphs
Abstract
Abstract: Clique graphs of several classes of graphs have been already characterized. Trees, interval graphs, chordal graphs, block graphs, clique-Helly graphs are some of them. However, no characterization o f clique graphs of circular-arc graphs and some of their subclasses is known. In this paper, we present a characterization theorem of clique graphs of Helly circular-arc graphs and prove that t his s ubclass of circular-arc graphs is contained in the intersection b etween p roper circular-arc graphs, clique-Helly circular-arc graphs and Helly circular-arc graphs. Furthermore, we prove properties about the 2-nd iterated clique graph of this family of graphs. Keywords: Circular-arc graphs, clique graphs, Helly circular-arc graphs, intersection graphs. 1- Introduction Consider a finite family of non-empty sets. The intersection graph o f this family is obtained b y representing each set by a vertex, two v ertices being connected b y an edge if and on ly if the corresponding sets intersect. Intersection graphs have received much attention in the study of algorithmic graph theory and their applications [6]. Well-known special classes of intersection graphs include interval graphs, chordal graphs, circular-arc graphs, p ermutation graphs, circle graphs, and so on. In this paper a c haracterization o f clique graphs of Helly circular-arc graphs is presented. We prove that clique graphs of this subclass of circular-arc graphs are contained in the intersection of three subclasses of circular-arc graphs and we a nalize properties about t he 2-nd iterated clique grapho f Helly circular-arc graphs. We shall denote the graph G by a pair (V(G),E(G)), where V(G) denotes a finite set of vertices of G and E(G) the set of edges connecting vertices of G. Let n = |V(G)| and m,= |E(G)|. The
Year
Venue
Keywords
2001
Ars Comb.
interval graph,chordal graph,graph theory
Field
DocType
Volume
Discrete mathematics,Block graph,Indifference graph,Combinatorics,Chordal graph,Cograph,Treewidth,Pathwidth,1-planar graph,Mathematics,Split graph
Journal
60
Citations 
PageRank 
References 
7
0.60
12
Authors
2
Name
Order
Citations
PageRank
Guillermo Durán129629.28
Min Chih Lin225921.22