×

The clique operator on circular-arc graphs. (English) Zbl 1209.05246

Summary: A circular-arc graph \(G\) 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 graph \(K(G)\) of a graph \(G\) is the intersection graph of its cliques. The iterated clique graph \(K^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.

MSC:

05C85 Graph algorithms (graph-theoretic aspects)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Hamelink, R. C., A partial characterization of clique graphs, J. Combin. Theory, 5, 192-197 (1968) · Zbl 0167.22203
[2] Roberts, F. S.; Spencer, J. H., A characterization of clique graphs, J. Combin. Theory Ser. B, 10, 102-108 (1971) · Zbl 0215.05801
[3] Szwarcfiter, J. L., A survey on clique graphs, (Recent Advances in Algorithms and Combinatorics. Recent Advances in Algorithms and Combinatorics, CMS Books Math./Ouvrages Math. SMC, vol. 11 (2003), Springer: Springer New York), 109-136 · Zbl 1027.05071
[4] Alcón, L.; Faria, L.; de Figueiredo, C. M.H.; Gutiérrez, M., Clique graph recognition is NP-complete, (Graph-Theoretic Concepts in Computer Science. Graph-Theoretic Concepts in Computer Science, Lecture Notes in Comput. Sci., vol. 4271 (2006), Springer), 269-277 · Zbl 1167.68403
[5] Hedman, B., Clique graphs of time graphs, J. Combin. Theory Ser. B, 37, 3, 270-278 (1984) · Zbl 0547.05056
[6] Larrión, F.; de Mello, C. P.; Morgana, A.; Neumann-Lara, V.; Pizaña, M. A., The clique operator on cographs and serial graphs, Discrete Math., 282, 1-3, 183-191 (2004) · Zbl 1042.05074
[7] de Mello, C. P.; Morgana, A.; Liverani, M., The clique operator on graphs with few \(P_4\)’s, Discrete Appl. Math., 154, 3, 485-492 (2006) · Zbl 1087.05045
[8] Neumann-Lara, V., On clique-divergent graphs, (Problèmes Combinatoires et Théorie des Graphes. Problèmes Combinatoires et Théorie des Graphes, Colloques Internationaux C.N.R.S., vol. 260 (1978)), 313-315 · Zbl 0413.05058
[9] Escalante, F., Über iterierte clique-graphen, Abh. Math. Sem. Univ. Hamburg, 39, 59-68 (1973) · Zbl 0266.05116
[10] Frías-Armenta, M. E.; Neumann-Lara, V.; Pizaña, M. A., Dismantlings and iterated clique graphs, Discrete Math., 282, 1-3, 263-265 (2004) · Zbl 1042.05070
[11] Golumbic, M. C.; Hammer, P. L., Stability in circular arc graphs, J. Algorithms, 9, 3, 314-320 (1988) · Zbl 0651.68083
[12] Larrión, F.; Neumann-Lara, V., A family of clique divergent graphs with linear growth, Graphs Combin., 13, 3, 263-266 (1997) · Zbl 0892.05041
[13] Brandstädt, A.; Le, V. B.; Spinrad, J. P., Graph classes: A survey, (SIAM Monographs on Discrete Mathematics and Applications (1999), Society for Industrial and Applied Mathematics (SIAM): Society for Industrial and Applied Mathematics (SIAM) Philadelphia, PA) · Zbl 0919.05001
[14] Spinrad, J. P., Efficient graph representations, (Fields Institute Monographs, vol. 19 (2003), American Mathematical Society: American Mathematical Society Providence, RI) · Zbl 1033.05001
[15] Kaplan, H.; Nussbaum, Y., Certifying algorithms for recognizing proper circular-arc graphs and unit circular-arc graphs, (Graph-Theoretic Concepts in Computer Science. Graph-Theoretic Concepts in Computer Science, Lecture Notes in Comput. Sci., vol. 4271 (2006), Springer: Springer Berlin), 289-300 · Zbl 1167.05333
[16] Kaplan, H.; Nussbaum, Y., A simpler linear-time recognition of circular-arc graphs, (Algorithm Theory—SWAT 2006. Algorithm Theory—SWAT 2006, Lecture Notes in Comput. Sci., vol. 4059 (2006), Springer), 41-52 · Zbl 1142.68622
[17] Lin, M. C.; Soulignac, F. J.; Szwarcfiter, J. L., Proper Helly circular-arc graphs, (Graph-Theoretic Concepts in Computer Science. Graph-Theoretic Concepts in Computer Science, Lecture Notes in Comput. Sci., vol. 4769 (2008), Springer), 248-257 · Zbl 1141.68539
[18] M.C. Lin, J.L. Szwarcfiter, Characterizations and recognition of circular-arc graphs and subclasses: A survey, Discrete Math., in press (doi:10.1016/j.disc.2008.04.003; M.C. Lin, J.L. Szwarcfiter, Characterizations and recognition of circular-arc graphs and subclasses: A survey, Discrete Math., in press (doi:10.1016/j.disc.2008.04.003 · Zbl 1228.05218
[19] McConnell, R. M., Linear-time recognition of circular-arc graphs, Algorithmica, 37, 2, 93-147 (2003) · Zbl 1060.68088
[20] Durán, G.; Lin, M. C., Clique graphs of Helly circular-arc graphs, Ars Combin., 60, 255-271 (2001) · Zbl 1072.05565
[21] Bonomo, F., Self-clique Helly circular-arc graphs, Discrete Math., 306, 6, 595-597 (2006) · Zbl 1087.05042
[22] Durán, G.; Lin, M. C.; Mera, S.; Szwarcfiter, J. L., Algorithms for clique-independent sets on subclasses of circular-arc graphs, Discrete Appl. Math., 154, 13, 1783-1790 (2006) · Zbl 1104.05054
[23] Lin, M. C.; McConnell, R.; Soulignac, F. J.; Szwarcfiter, J. L., On cliques of Helly circular-arc graphs, (Proceedings of the IV Latin-American Algorithms, Graphs and Optimization Symposium - LAGOS’ 2007. Proceedings of the IV Latin-American Algorithms, Graphs and Optimization Symposium - LAGOS’ 2007, Electronic Notes in Disc. Math., vol. 30 (2008), Elsevier), 117-122 · Zbl 1341.05196
[24] F.F. Dragan, Center of graphs and the Helly property, Ph.D. Thesis, Moldava State University, Chisinau, Moldava, 1989; F.F. Dragan, Center of graphs and the Helly property, Ph.D. Thesis, Moldava State University, Chisinau, Moldava, 1989
[25] Szwarcfiter, J. L., Recognizing clique-Helly graphs, Ars Combin., 45, 29-32 (1997) · Zbl 0933.05127
[26] Deng, X.; Hell, P.; Huang, J., Linear-time representation algorithms for proper circular-arc graphs and proper interval graphs, SIAM J. Comput., 25, 2, 390-403 (1996) · Zbl 0858.05094
[27] Lin, M. C.; Szwarcfiter, J. L., Unit circular-arc graph representations and feasible circulations, SIAM J. Discrete Math., 22, 1, 409-423 (2008) · Zbl 1232.05145
[28] Lin, M. C.; Soulignac, F. J.; Szwarcfiter, J. L., A simple linear time algorithm for the isomorphism problem on proper circular-arc graphs, (Algorithm Theory—SWAT 2008. Algorithm Theory—SWAT 2008, Lecture Notes in Comput. Sci., vol. 5124 (2008), Springer), 355-366 · Zbl 1155.05339
[29] Larrión, F.; Neumann-Lara, V.; Pizaña, M. A., On expansive graphs, European J. Combin., 30, 2, 372-379 (2009) · Zbl 1189.05116
[30] Prisner, E., Convergence of iterated clique graphs, Discrete Math., 103, 2, 199-207 (1992) · Zbl 0766.05096
[31] Nowakowski, R.; Winkler, P., Vertex-to-vertex pursuit in a graph, Discrete Math., 43, 2-3, 235-239 (1983) · Zbl 0508.05058
[32] A. Quilliot, 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, 1983; A. Quilliot, 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, 1983
[33] Spinrad, J. P., Recognizing quasi-triangulated graphs, Discrete Appl. Math., 138, 1-2, 203-213 (2004) · Zbl 1034.05036
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.