×

The clique operator on matching and chessboard graphs. (English) Zbl 1207.05158

Summary: Given positive integers \(m,n\), we consider the graphs \(G_n\) and \(G_{m,n}\) whose simplicial complexes of complete subgraphs are the well-known matching complex \(M_n\) and chessboard complex \(M_{m,n}\). Those are the matching and chessboard graphs. We determine which matching and chessboard graphs are clique-Helly. If the parameters are small enough, we show that these graphs (even if not clique-Helly) are homotopy equivalent to their clique graphs. We determine the clique behavior of the chessboard graph \(G_{m,n}\) in terms of \(m\) and \(n\), and show that \(G_{m,n}\) is clique-divergent if and only if it is not clique-Helly. We give partial results for the clique behavior of the matching graph \(G_n\).

MSC:

05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
05C60 Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.)
05E45 Combinatorial aspects of simplicial complexes

Software:

Homology; GAP
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Alperin, J. L.; Glauberman, G., Coverings and coverings, J. Aust. Math. Soc. Ser. A, 57, 125-128 (1994) · Zbl 0820.20029
[2] Björner, A.; Lovász, L.; Vrećica, S. T.; Živaljević, R. T., Chessboard complexes and matching complexes, J. London Math. Soc., 49, 2, 25-39 (1994) · Zbl 0790.57014
[3] Bouc, S., Homologie de certains ensembles de 2-sous-groupes des groupes symétriques, J. Algebra, 150, 158-186 (1992) · Zbl 0786.55005
[4] Buset, D., Graphs which are locally a cube, Discrete Math., 46, 221-226 (1983) · Zbl 0532.05050
[5] de Mello, C. P.; Morgana, A., The clique operator on extended \(P_4\)-sparse graphs, Mat. Contemp., 25, 33-47 (2003), The Latin-American Workshop on Cliques in Graphs (Rio de Janeiro, 2002) · Zbl 1050.05101
[6] Dong, X.; Wachs, M. L., Combinatorial Laplacian of the matching complex, Electron. J. Combin., 9 (2002), Research Paper 17, 11 pp. (electronic) · Zbl 0985.05052
[7] F.F. Dragan, Centers of graphs and the Helly property, Ph.D. Thesis, Moldava State University, Chisinaˇu, Moldava, 1989 (in Russian); F.F. Dragan, Centers of graphs and the Helly property, Ph.D. Thesis, Moldava State University, Chisinaˇu, Moldava, 1989 (in Russian)
[8] Escalante, F., Über iterierte Clique-Graphen, Abh. Math. Sem. Univ. Hamburg, 39, 59-68 (1973) · Zbl 0266.05116
[9] The GAP Group. GAP — Groups, Algorithms, and Programming, Version 4.3, 2002. http://www.gap-system.org; The GAP Group. GAP — Groups, Algorithms, and Programming, Version 4.3, 2002. http://www.gap-system.org
[10] P.F. Garst, Cohen-Macaulay complexes and group actions, Ph.D. Thesis, University of Wisconsin, 1979; P.F. Garst, Cohen-Macaulay complexes and group actions, Ph.D. Thesis, University of Wisconsin, 1979
[11] Godsil, C.; Royle, G., Algebraic graph theory, (Graduate Texts in Mathematics, vol. 207 (2001), Springer-Verlag: Springer-Verlag New York) · Zbl 0968.05002
[12] Hall, J. I., Locally Petersen graphs, J. Graph Theory, 4, 173-187 (1980) · Zbl 0407.05041
[13] F. Heckenbach, J.G. Dumas, D. Saunders, V. Welker, Simplicial Homology, a (proposed) GAP share package, 2001. http://www.eecis.udel.edu/ dumas/Homology/; F. Heckenbach, J.G. Dumas, D. Saunders, V. Welker, Simplicial Homology, a (proposed) GAP share package, 2001. http://www.eecis.udel.edu/ dumas/Homology/
[14] Holton, D. A.; Sheehan, J., (The Petersen Graph. The Petersen Graph, Australian Mathematical Society Lecture Series, vol. 7 (1993), Cambridge University Press: Cambridge University Press Cambridge) · Zbl 0781.05001
[15] 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, 183-191 (2004) · Zbl 1042.05074
[16] Larrión, F.; Neumann-Lara, V., Locally \(C_6\) graphs are clique divergent, Discrete Math., 215, 159-170 (2000) · Zbl 0961.05056
[17] Larrión, F.; Neumann-Lara, V.; Pizaña, M. A., On the homotopy type of the clique graph, J. Brazilian Comp. Soc., 7, 69-73 (2002) · Zbl 1010.05050
[18] Larrión, F.; Neumann-Lara, V.; Pizaña, M. A., Whitney triangulations, local girth and iterated clique graphs, Discrete Math., 258, 123-135 (2002) · Zbl 1010.05050
[19] Larrión, F.; Neumann-Lara, V.; Pizaña, M. A., Clique divergent clockwork graphs and partial orders, Discrete Appl. Math., 141, 195-207 (2004) · Zbl 1042.05072
[20] F. Larrión, V. Neumann-Lara, M.A. Pizaña, On expansive graphs, 2005 (submitted for publication). Available at: http://xamanek.izt.uam.mx/map/papers/expan07.pdf; F. Larrión, V. Neumann-Lara, M.A. Pizaña, On expansive graphs, 2005 (submitted for publication). Available at: http://xamanek.izt.uam.mx/map/papers/expan07.pdf
[21] V. Neumann-Lara, On clique-divergent graphs, in: Problèmes combinatories et Théorie de Graphes, number 260, pp. 313-315, Colloques Internationaux C.N.R.S., Orsay, France, 1978; V. Neumann-Lara, On clique-divergent graphs, in: Problèmes combinatories et Théorie de Graphes, number 260, pp. 313-315, Colloques Internationaux C.N.R.S., Orsay, France, 1978 · Zbl 0413.05058
[22] Prisner, E., Convergence of iterated clique graphs, Discrete Math., 103, 199-207 (1992) · Zbl 0766.05096
[23] Shareshian, J., Hypergraph matching complexes and Quillen complexes of symmetric groups, J. Combin. Theory Ser. A, 106, 299-314 (2004) · Zbl 1059.20019
[24] Shareshian, J.; Wachs, M., Torsion in the matching complex and chessboard complex, Adv. Math., 212, 525-570 (2007) · Zbl 1117.05110
[25] 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
[26] Szwarcfiter, J. L., Recognizing clique-Helly graphs, Ars Combin., 45, 29-32 (1997) · Zbl 0933.05127
[27] Wachs, M. L., Topology of matching, chessboard, and general bounded degree graph complexes, Algebra Universalis, 49, 345-385 (2003), Dedicated to the memory of Gian-Carlo Rota · Zbl 1092.05511
[28] Živaljević, R. T.; Vrećica, S. T., The colored Tverberg’s problem and complexes of injective functions, J. Combin. Theory Ser. A, 61, 309-318 (1992) · Zbl 0782.52003
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.