Navegar

Colección

Datos Estadísticas

Artículo

Este artículo es de Acceso Abierto y puede ser descargado en su versión final desde nuestro repositorio
Consulte el artículo en la página del editor
Consulte la política de Acceso Abierto del editor

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

Registro:

Documento: Artículo
Título:The clique operator on circular-arc graphs
Autor:Lin, M.C.; Soulignac, F.J.; Szwarcfiter, J.L.
Filiación:Departamento de Computación, FCEN, Universidad de Buenos Aires, Buenos Aires, Argentina
Universidade Federal do Rio de Janeiro, Inst. de Matemática, NCE, Caixa Postal 2324, 20001-970 Rio de Janeiro, RJ, Brazil
Palabras clave: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
Año:2010
Volumen:158
Número:12
Página de inicio:1259
Página de fin:1267
DOI: http://dx.doi.org/10.1016/j.dam.2009.01.019
Título revista:Discrete Applied Mathematics
Título revista abreviado:Discrete Appl Math
ISSN:0166218X
CODEN:DAMAD
PDF:https://bibliotecadigital.exactas.uba.ar/download/paper/paper_0166218X_v158_n12_p1259_Lin.pdf
Registro:https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_0166218X_v158_n12_p1259_Lin

Referencias:

  • Hamelink, R.C., A partial characterization of clique graphs (1968) J. Combin. Theory, 5, pp. 192-197
  • Roberts, F.S., Spencer, J.H., A characterization of clique graphs (1971) J. Combin. Theory Ser. B, 10, pp. 102-108
  • Szwarcfiter, J.L., A survey on clique graphs (2003) CMS Books Math./Ouvrages Math. SMC, 11, pp. 109-136. , Recent Advances in Algorithms and Combinatorics, Springer, New York
  • Alcón, L., Faria, L., de Figueiredo, C.M.H., Gutiérrez, M., Clique graph recognition is NP-complete (2006) Lecture Notes in Comput. Sci., 4271, pp. 269-277. , Graph-Theoretic Concepts in Computer Science, Springer
  • Hedman, B., Clique graphs of time graphs (1984) J. Combin. Theory Ser. B, 37 (3), pp. 270-278
  • Larrión, F., de Mello, C.P., Morgana, A., Neumann-Lara, V., Pizaña, M.A., The clique operator on cographs and serial graphs (2004) Discrete Math., 282 (1-3), pp. 183-191
  • de Mello, C.P., Morgana, A., Liverani, M., The clique operator on graphs with few P4's (2006) Discrete Appl. Math., 154 (3), pp. 485-492
  • Neumann-Lara, V., On clique-divergent graphs (1978) Colloques Internationaux C.N.R.S., 260, pp. 313-315. , Problèmes Combinatoires et Théorie des Graphes
  • Escalante, F., Über iterierte clique-graphen (1973) Abh. Math. Sem. Univ. Hamburg, 39, pp. 59-68
  • Frías-Armenta, M.E., Neumann-Lara, V., Pizaña, M.A., Dismantlings and iterated clique graphs (2004) Discrete Math., 282 (1-3), pp. 263-265
  • Golumbic, M.C., Hammer, P.L., Stability in circular arc graphs (1988) J. Algorithms, 9 (3), pp. 314-320
  • Larrión, F., Neumann-Lara, V., A family of clique divergent graphs with linear growth (1997) Graphs Combin., 13 (3), pp. 263-266
  • Brandstädt, A., Le, V.B., Spinrad, J.P., Graph classes: A survey (1999) SIAM Monographs on Discrete Mathematics and Applications, , Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA
  • Spinrad, J.P., Efficient graph representations (2003) Fields Institute Monographs, 19. , American Mathematical Society, Providence, RI
  • Kaplan, H., Nussbaum, Y., Certifying algorithms for recognizing proper circular-arc graphs and unit circular-arc graphs (2006) Lecture Notes in Comput. Sci., 4271, pp. 289-300. , Graph-Theoretic Concepts in Computer Science, Springer, Berlin
  • Kaplan, H., Nussbaum, Y., A simpler linear-time recognition of circular-arc graphs (2006) Lecture Notes in Comput. Sci., 4059, pp. 41-52. , Algorithm Theory-SWAT 2006, Springer
  • Lin, M.C., Soulignac, F.J., Szwarcfiter, J.L., Proper Helly circular-arc graphs (2008) Lecture Notes in Comput. Sci., 4769, pp. 248-257. , Graph-Theoretic Concepts in Computer Science, Springer
  • Lin, M.C., Szwarcfiter, J.L., Characterizations and recognition of circular-arc graphs and subclasses: A survey Discrete Math, , in press doi:10.1016/j.disc.2008.04.003
  • McConnell, R.M., Linear-time recognition of circular-arc graphs (2003) Algorithmica, 37 (2), pp. 93-147
  • Durán, G., Lin, M.C., Clique graphs of Helly circular-arc graphs (2001) Ars Combin., 60, pp. 255-271
  • Bonomo, F., Self-clique Helly circular-arc graphs (2006) Discrete Math., 306 (6), pp. 595-597
  • Durán, G., Lin, M.C., Mera, S., Szwarcfiter, J.L., Algorithms for clique-independent sets on subclasses of circular-arc graphs (2006) Discrete Appl. Math., 154 (13), pp. 1783-1790
  • Lin, M.C., McConnell, R., Soulignac, F.J., Szwarcfiter, J.L., On cliques of Helly circular-arc graphs (2008) Electronic Notes in Disc. Math., 30, pp. 117-122. , Proceedings of the IV Latin-American Algorithms, Graphs and Optimization Symposium - LAGOS' 2007, Elsevier
  • Dragan, F.F., (1989) Center of graphs and the Helly property, , Ph.D. Thesis, Moldava State University, Chisinau, Moldava
  • Szwarcfiter, J.L., Recognizing clique-Helly graphs (1997) Ars Combin., 45, pp. 29-32
  • Deng, X., Hell, P., Huang, J., Linear-time representation algorithms for proper circular-arc graphs and proper interval graphs (1996) SIAM J. Comput., 25 (2), pp. 390-403
  • Lin, M.C., Szwarcfiter, J.L., Unit circular-arc graph representations and feasible circulations (2008) SIAM J. Discrete Math., 22 (1), pp. 409-423
  • Lin, M.C., Soulignac, F.J., Szwarcfiter, J.L., A simple linear time algorithm for the isomorphism problem on proper circular-arc graphs (2008) Lecture Notes in Comput. Sci., 5124, pp. 355-366. , Algorithm Theory-SWAT 2008, Springer
  • Larrión, F., Neumann-Lara, V., Pizaña, M.A., On expansive graphs (2009) European J. Combin., 30 (2), pp. 372-379
  • Prisner, E., Convergence of iterated clique graphs (1992) Discrete Math., 103 (2), pp. 199-207
  • Nowakowski, R., Winkler, P., Vertex-to-vertex pursuit in a graph (1983) Discrete Math., 43 (2-3), pp. 235-239
  • Quilliot, A., (1983) Homomorphismes, points fixes rtractions et jeux de poursuite dans les graphes, les ensembles ordonns et les espaces mtriques, , Ph.D. Thesis, Universit de Paris VI, France
  • Spinrad, J.P., Recognizing quasi-triangulated graphs (2004) Discrete Appl. Math., 138 (1-2), pp. 203-213

Citas:

---------- APA ----------
Lin, M.C., Soulignac, F.J. & Szwarcfiter, J.L. (2010) . The clique operator on circular-arc graphs. Discrete Applied Mathematics, 158(12), 1259-1267.
http://dx.doi.org/10.1016/j.dam.2009.01.019
---------- CHICAGO ----------
Lin, M.C., Soulignac, F.J., Szwarcfiter, J.L. "The clique operator on circular-arc graphs" . Discrete Applied Mathematics 158, no. 12 (2010) : 1259-1267.
http://dx.doi.org/10.1016/j.dam.2009.01.019
---------- MLA ----------
Lin, M.C., Soulignac, F.J., Szwarcfiter, J.L. "The clique operator on circular-arc graphs" . Discrete Applied Mathematics, vol. 158, no. 12, 2010, pp. 1259-1267.
http://dx.doi.org/10.1016/j.dam.2009.01.019
---------- VANCOUVER ----------
Lin, M.C., Soulignac, F.J., Szwarcfiter, J.L. The clique operator on circular-arc graphs. Discrete Appl Math. 2010;158(12):1259-1267.
http://dx.doi.org/10.1016/j.dam.2009.01.019