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 biclique is a maximal induced complete bipartite subgraph of a graph. We investigate the intersection structure of edge-sets of bicliques in a graph. Specifically, we study the associated edge-biclique hypergraph whose hyperedges are precisely the edge-sets of all bicliques. We characterize graphs whose edge-biclique hypergraph is conformal (i.e., it is the clique hypergraph of its 2-section) by means of a single forbidden induced obstruction, the triangular prism. Using this result, we characterize graphs whose edge-biclique hypergraph is Helly and provide a polynomial time recognition algorithm. We further study a hereditary version of this property and show that it also admits polynomial time recognition, and, in fact, is characterized by a finite set of forbidden induced subgraphs. We conclude by describing some interesting properties of the 2-section graph of the edge-biclique hypergraph. © 2011 Elsevier B.V. All rights reserved.

Registro:

Documento: Artículo
Título:On edge-sets of bicliques in graphs
Autor:Groshaus, M.; Hell, P.; Stacho, J.
Filiación:Universidad de Buenos Aires, Facultad de Ciencias Exactas y Naturales, Departamento de Computación, Buenos Aires, Argentina
Simon Fraser University, School of Computing Science, 8888 University Drive, Burnaby, BC V5A 1S6, Canada
Wilfrid Laurier University, Department of Physics and Computer Science, 75 University Ave W, Waterloo, ON N2L 3C5, Canada
University of Warwick, Mathematics Institute, Zeeman Building, Coventry, CV4 7AL, United Kingdom
Palabras clave:2-section; Biclique; Clique graph; Conformal; Helly; Hypergraph; Intersection graph; 2-section; Biclique; Clique graphs; Conformal; Helly; Hypergraph; Intersection graph; Combinatorial mathematics; Mathematical techniques; Polynomial approximation
Año:2012
Volumen:160
Número:18
Página de inicio:2698
Página de fin:2708
DOI: http://dx.doi.org/10.1016/j.dam.2012.02.004
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_v160_n18_p2698_Groshaus.pdf
Registro:https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_0166218X_v160_n18_p2698_Groshaus

Referencias:

  • Alcón, L., Faria, L., De Figueiredo, C.M., Gutierrez, M., The complexity of clique graph recognition (2009) Theoretical Computer Science, 410, pp. 2072-2083
  • Beineke, L.W., Characterizations of derived graphs (1970) Journal of Combinatorial Theory, 9, pp. 129-135
  • Berge, C., (1989) Hypergraphs, North-Holland Mathematical Library, 45. , Elsevier Science Publishers B.V Amsterdam
  • Calamoneri, T., Petreschi, R., Edge-clique graphs and the λ-coloring problem (2001) Journal of the Brazilian Computer Society, 7, pp. 38-47
  • Cerioli, M.R., Clique graphs and edge-clique graphs (2003) Electronic Notes in Discrete Mathematics, 13, pp. 34-37
  • Cerioli, M.R., Szwarcfiter, J., Edge clique graphs and some classes of chordal graphs (2002) Discrete Mathematics, 242, pp. 31-39
  • Cerioli, M.R., Szwarcfiter, J., A characterization of edge clique graphs Manuscript
  • Chartrand, G., Kapoor, S.F., McKee, T.A., Saba, F., Edge clique graphs (1991) Graphs and Combinatorics, 7, pp. 253-264
  • Golumbic, M.C., (1980) Algorithmic Graph Theory and Perfect Graphs, , Academic Press New York
  • Golumbic, M.C., Jamison, R.E., The edge intersection graphs of paths in a tree (1985) Journal Combinatorial Theory B, 38, pp. 8-22
  • Groshaus, M., Szwarcfiter, J., Biclique-Helly graphs (2007) Graphs and Combinatorics, 23, pp. 633-645
  • Groshaus, M., Szwarcfiter, J., On hereditary Helly classes of graphs (2008) Discrete Mathematics and Theoretical Computer Science, 10, pp. 71-78
  • Groshaus, M., Szwarcfiter, J., Biclique graphs and biclique matrices (2010) Journal of Graph Theory, 63, pp. 1-16
  • Harary, F., Holzmann, C., Line graphs of bipartite graphs (1974) Revista de la Sociedad Matematica de Chile, 1, pp. 19-22
  • Lin, M.C., Szwarcfiter, J.L., Faster recognition of clique-Helly and hereditary clique-Helly graphs (2007) Information Processing Letters, 103, pp. 40-43
  • Prisner, E., Hereditary clique-Helly graphs (1993) Journal of Combinatorial Mathematics and Combinatorial Computing, 14, pp. 216-220
  • Raychaudhuri, A., Intersection number and edge-clique graphs of chordal and strongly chordal graphs (1988) Congressus Numerantium, 67, pp. 197-204
  • Raychaudhuri, A., Edge-clique graphs of some important classes of graphs (1991) Ars Combinatoria, 32, pp. 269-278
  • Szpilrajn-Marczewski, E., Sur deux propriétés des classes d'ensembles (1945) Fundamenta Mathematicae, 33, pp. 303-307
  • West, D., (1996) Introduction to Graph Theory, , Prentice Hall

Citas:

---------- APA ----------
Groshaus, M., Hell, P. & Stacho, J. (2012) . On edge-sets of bicliques in graphs. Discrete Applied Mathematics, 160(18), 2698-2708.
http://dx.doi.org/10.1016/j.dam.2012.02.004
---------- CHICAGO ----------
Groshaus, M., Hell, P., Stacho, J. "On edge-sets of bicliques in graphs" . Discrete Applied Mathematics 160, no. 18 (2012) : 2698-2708.
http://dx.doi.org/10.1016/j.dam.2012.02.004
---------- MLA ----------
Groshaus, M., Hell, P., Stacho, J. "On edge-sets of bicliques in graphs" . Discrete Applied Mathematics, vol. 160, no. 18, 2012, pp. 2698-2708.
http://dx.doi.org/10.1016/j.dam.2012.02.004
---------- VANCOUVER ----------
Groshaus, M., Hell, P., Stacho, J. On edge-sets of bicliques in graphs. Discrete Appl Math. 2012;160(18):2698-2708.
http://dx.doi.org/10.1016/j.dam.2012.02.004