The clique operator on circular-arc graphs

Mostrar todas las versiones(3)

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 w...

Descripción completa

Guardado en:

Detalles Bibliográficos
Autores principales:	Lin, M.C., Soulignac, F.J., Szwarcfiter, J.L.
Formato:	Artículo publishedVersion
Publicado:	2010
Materias:	Algorithms Clique graphs Helly circular-arc graphs K-behavior Proper Helly circular-arc graphs Circular-arc graph Complete solutions Graph G Intersection graph Linear time Recognition algorithm Graph theory Mathematical operators Graphic methods
Acceso en línea:	http://hdl.handle.net/20.500.12110/paper_0166218X_v158_n12_p1259_Lin https://repositoriouba.sisbi.uba.ar/gsdl/cgi-bin/library.cgi?a=d&c=artiaex&d=paper_0166218X_v158_n12_p1259_Lin_oai
Aporte de:	Repositorio Digital de la Universidad de Buenos Aires (UBA) de Universidad de Buenos Aires

id	I28-R145-paper_0166218X_v158_n12_p1259_Lin_oai
record_format	dspace
spelling	I28-R145-paper_0166218X_v158_n12_p1259_Lin_oai2024-08-16 Lin, M.C. Soulignac, F.J. Szwarcfiter, J.L. 2010 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 graphKi (G) of G is defined by K0 (G) = G and 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 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. © 2009 Elsevier B.V. All rights reserved. Fil:Lin, M.C. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. Fil:Soulignac, F.J. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. application/pdf http://hdl.handle.net/20.500.12110/paper_0166218X_v158_n12_p1259_Lin info:eu-repo/semantics/openAccess http://creativecommons.org/licenses/by/2.5/ar Discrete Appl Math 2010;158(12):1259-1267 Algorithms Clique graphs Helly circular-arc graphs K-behavior Proper Helly circular-arc graphs Circular-arc graph Clique graphs Complete solutions Graph G Intersection graph K-behavior Linear time Recognition algorithm Algorithms Graph theory Mathematical operators Graphic methods The clique operator on circular-arc graphs info:eu-repo/semantics/article info:ar-repo/semantics/artículo info:eu-repo/semantics/publishedVersion https://repositoriouba.sisbi.uba.ar/gsdl/cgi-bin/library.cgi?a=d&c=artiaex&d=paper_0166218X_v158_n12_p1259_Lin_oai
institution	Universidad de Buenos Aires
institution_str	I-28
repository_str	R-145
collection	Repositorio Digital de la Universidad de Buenos Aires (UBA)
topic	Algorithms Clique graphs Helly circular-arc graphs K-behavior Proper Helly circular-arc graphs Circular-arc graph Clique graphs Complete solutions Graph G Intersection graph K-behavior Linear time Recognition algorithm Algorithms Graph theory Mathematical operators Graphic methods
spellingShingle	Algorithms Clique graphs Helly circular-arc graphs K-behavior Proper Helly circular-arc graphs Circular-arc graph Clique graphs Complete solutions Graph G Intersection graph K-behavior Linear time Recognition algorithm Algorithms Graph theory Mathematical operators Graphic methods Lin, M.C. Soulignac, F.J. Szwarcfiter, J.L. The clique operator on circular-arc graphs
topic_facet	Algorithms Clique graphs Helly circular-arc graphs K-behavior Proper Helly circular-arc graphs Circular-arc graph Clique graphs Complete solutions Graph G Intersection graph K-behavior Linear time Recognition algorithm Algorithms Graph theory Mathematical operators Graphic methods
description	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 graphKi (G) of G is defined by K0 (G) = G and 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 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. © 2009 Elsevier B.V. All rights reserved.
format	Artículo Artículo publishedVersion
author	Lin, M.C. Soulignac, F.J. Szwarcfiter, J.L.
author_facet	Lin, M.C. Soulignac, F.J. Szwarcfiter, J.L.
author_sort	Lin, M.C.
title	The clique operator on circular-arc graphs
title_short	The clique operator on circular-arc graphs
title_full	The clique operator on circular-arc graphs
title_fullStr	The clique operator on circular-arc graphs
title_full_unstemmed	The clique operator on circular-arc graphs
title_sort	clique operator on circular-arc graphs
publishDate	2010
url	http://hdl.handle.net/20.500.12110/paper_0166218X_v158_n12_p1259_Lin https://repositoriouba.sisbi.uba.ar/gsdl/cgi-bin/library.cgi?a=d&c=artiaex&d=paper_0166218X_v158_n12_p1259_Lin_oai
work_keys_str_mv	AT linmc thecliqueoperatoroncirculararcgraphs AT soulignacfj thecliqueoperatoroncirculararcgraphs AT szwarcfiterjl thecliqueoperatoroncirculararcgraphs AT linmc cliqueoperatoroncirculararcgraphs AT soulignacfj cliqueoperatoroncirculararcgraphs AT szwarcfiterjl cliqueoperatoroncirculararcgraphs
_version_	1809356996727537664

The clique operator on circular-arc graphs

Ejemplares similares