Portal de Periódicos da CAPES

On the Iterated Biclique Operator

2012; Wiley; Volume: 73; Issue: 2 Linguagem: Inglês

10.1002/jgt.21666

1097-0118

Marina Groshaus, Leandro Montero,

Graph Labeling and Dimension Problems

Journal of Graph TheoryVolume 73, Issue 2 p. 181-190 Original Article On the Iterated Biclique Operator Marina Groshaus, Marina Groshaus [email protected] Search for more papers by this authorLeandro P. Montero, Leandro P. MonteroSearch for more papers by this author Marina Groshaus, Marina Groshaus [email protected] Search for more papers by this authorLeandro P. Montero, Leandro P. MonteroSearch for more papers by this author First published: 03 August 2012 https://doi.org/10.1002/jgt.21666Citations: 17 Contract grant sponsors: Prosul-Cnpq; UBACyT; PICT ANPCyT; PID Conicet Grant (Argentina); Contract grant numbers: 490333/04-4; X184; X212; 11-09112 (to M. G.); Contract grant sponsor: Conicet Grant (Argentina) (to L. P. M.). Read the full textAboutPDF ToolsRequest permissionExport citationAdd to favoritesTrack citation ShareShare Give accessShare full text accessShare full-text accessPlease review our Terms and Conditions of Use and check box below to share full-text version of article.I have read and accept the Wiley Online Library Terms and Conditions of UseShareable LinkUse the link below to share a full-text version of this article with your friends and colleagues. Learn more.Copy URL Share a linkShare onEmailFacebookTwitterLinkedInRedditWechat Abstract A biclique of a graph G is a maximal induced complete bipartite subgraph of G. The biclique graph of G, denoted by , is the intersection graph of the bicliques of G. We say that a graph G diverges (or converges or is periodic) under an operator F whenever ( for some m, or for some k and , respectively). Given a graph G, the iterated biclique graph of G, denoted by , is the graph obtained by applying the biclique operator k successive times to G. In this article, we study the iterated biclique graph of G. In particular, we classify the different behaviors of when the number of iterations k grows to infinity. That is, we prove that a graph either diverges or converges under the biclique operator. We give a forbidden structure characterization of convergent graphs, which yield a polynomial time algorithm to decide if a given graph diverges or converges. This is in sharp contrast with the situsation for the better known clique operator, where it is not even known if the corresponding problem is decidable. © 2012 Wiley Periodicals, Inc. J. Graph Theory 73: 181–190, 2013 REFERENCES 1L. Alcón, L. Faria, C. M. H. de Figueiredo, and M. Gutierrez, Clique graph recognition is NP-complete, Graph Theor Concepts Comput Sci 4271 (2006), 269–277. 2H.-J. Bandelt and E. Prisner, Clique graphs and Helly graphs, J Combin Theory Ser B 51(1) (1991), 34–45. 3K. Booth and G. Lueker, Testing for the consecutive ones property interval graphs, and graph planarity using PQ-tree algorithms, J Comput Syst. Sci 13(3) (1976), 335–379. 4A. Brandstädt, V. Le, and J. P. Spinrad, Graph Classes: a Survey, SIAM Monographs on Discrete Mathematics and Applications, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1999. 5C. P. de Mello, A. Morgana, and M. Liverani, The clique operator on graphs with few P4's, Discrete Appl Math 154(3) (2006), 485–492. 6V. M. F. Dias, C. M. H. de Figueiredo, and J. L. Szwarcfiter, Generating bicliques of a graph in lexicographic order, Theor Comput Sci 337(1-3) (2005), 240–248. 7V. M. F. Dias, C. M. H. de Figueiredo, and J. L. Szwarcfiter, On the generation of bicliques of a graph, Discrete Appl Math 155(14) (2007), 1826–1832. 8F. Escalante, Über iterierte Clique-Graphen, Abh Math Sem Univ Hamburg 39 (1973), 59–68. 9L. F., M. A. Pizaña, and R. Villarroel-Flores, Equivariant collapses and the homotopy type of iterated clique graphs, Discrete Math 308 (2008), 3199–3207. 10M. E. Frías-Armenta, V. Neumann-Lara, and M. A. Pizaña, Dismantlings and iterated clique graphs, Discrete Math 282(1-3) (2004), 263–265. 11D. R. Fulkerson and O. A. Gross, Incidence matrices and interval graphs, Pacific J Math 15 (1965), 835–855. 12F. Gavril, The intersection graphs of subtrees in trees are exactly the chordal graphs, J Combin Theory Ser B 16 (1974), 47–56. 13M. Groshaus and J. L. Szwarcfiter, Biclique graphs and biclique matrices, J Graph Theory 63(1) (2010), 1–16. 14M. E. Groshaus, Bicliques, cliques, neighborhoods y la propiedad de Helly, Ph.D. Thesis, Universidad de Buenos Aires, 2006. 15R. C. Hamelink, A partial characterization of clique graphs, J Combin Theory 5 (1968), 192–197. 16S. T. Hedetniemi and P. J. Slater, Line graphs of triangleless graphs and iterated clique graphs, In: Graph Theory and Applications (Proc. Conf., Western Michigan Univ., Kalamazoo, Mich., 1972; dedicated to the memory of J. W. T. Youngs), Lecture Notes in Mathematics, Vol. 303, Springer, Berlin, 1972, pp. 139–147. 17F. Larrión, C. P. de Mello, A. Morgana, V. Neumann-Lara, and M. A. Pizaña, The clique operator on cographs and serial graphs, Discrete Math 282(1-3) (2004), 183–191. 18F. Larrión and V. Neumann-Lara, A family of clique divergent graphs with linear growth, Graphs Combin 13(3) (1997), 263–266. 19F. Larrión and V. Neumann-Lara, Clique divergent graphs with unbounded sequence of diameters, Discrete Math 197/198 (1999), 491–501, 16th British Combinatorial Conference (London, 1997). 20F. Larrión and V. Neumann-Lara, Locally C6 graphs are clique divergent, Discrete Math 215(1-3) (2000), 159–170. 21F. Larrión, V. Neumann-Lara, and M. A. Pizaña, Whitney triangulations local girth and iterated clique graphs, Discrete Math 258(1-3) (2002), 123–135. 22P. G. H. Lehot, An optimal algorithm to detect a line graph and output its root graph, J ACM 21(4) (1974), 569–575. 23T. A. McKee and F. R. McMorris, Topics in Intersection Graph Theory, SIAM Monographs on Discrete Mathematics and Applications, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1999. 24V. Neumann Lara, Clique divergence in graphs, In: Algebraic Methods in Graph Theory, Vol. I, II (Szeged, 1978), volume 25 of Colloq. Math. Soc. János Bolyai, North-Holland, Amsterdam, 1981, pp. 563–569. 25M. A. Pizaña, The icosahedron is clique divergent, Discrete Math 262(1-3) (2003), 229–239. 26F. S. Roberts and J. H. Spencer, A characterization of clique graphs, J Combin Theory Ser B 10 (1971), 102–108. 27E. Szpilrajn-Marczewski, Sur deux propriétés des classes d'ensembles, Fund Math 33 (1945), 303–307. Citing Literature Volume73, Issue2June 2013Pages 181-190 ReferencesRelatedInformation