Navegar

Colección

Datos Estadísticas

Artículo

Bondy, A.; Durán, G.; Lin, M.C.; Szwarcfiter, J.L. "Self-Clique Graphs and Matrix Permutations" (2003) Journal of Graph Theory. 44(3):178-192
Estamos trabajando para incorporar este artículo al repositorio
Consulte el artículo en la página del editor
Consulte la política de Acceso Abierto del editor

Abstract:

The clique graph of a graph is the intersection graph of its (maximal) cliques. A graph is self-clique when it is isomorphic with its clique graph, and is clique-Helly when its cliques satisfy the Helly property. We prove that a graph is clique-Helly and self-clique if and only if it admits a quasi-symmetric clique matrix, that is, a clique matrix whose families of row and column vectors are identical. We also give a characterization of such graphs in terms of vertex-clique duality. We describe new classes of self-clique and 2-self-clique graphs. Further, we consider some problems on permuted matrices (matrices obtained by permuting the rows and/or columns of a given matrix). We prove that deciding whether a (0,1)-matrix admits a symmetric (quasi-symmetric) permuted matrix is graph (hypergraph) isomorphism Complete. ©2003 Wiley Periodicals, Inc.

Registro:

Documento: Artículo
Título:Self-Clique Graphs and Matrix Permutations
Autor:Bondy, A.; Durán, G.; Lin, M.C.; Szwarcfiter, J.L.
Filiación:UFR De Mathématiques, Univ. Claude-Bernard Lyon 1, Villeurbanne, France
Equipe Combinatoire CNRS, Université Paris 6, Paris, France
Departemento de Ing. Industrial, Fac. de Cie. Fis./Matemat., Universidad de Chile, santiago, Chile
Departemento de Computación, Fac. de Cie. Exactas y Naturales, Universidad de Buenos Aires, Buenos Aires, Argentina
Instituto de Matemática, NCE, Univ. Federal do Rio de Janeiro, Caixa Postal 2324, 20001-970 Rio de Janeiro, RJ, Brazil
Palabras clave:Clique graph; Clique-Helly graph; Computational complexity; Permuted matrix; Selfclique graph; Algorithms; Computational complexity; Matrix algebra; Vectors; Clique graphs; Matrix permutations; Graph theory
Año:2003
Volumen:44
Número:3
Página de inicio:178
Página de fin:192
DOI: http://dx.doi.org/10.1002/jgt.10496
Título revista:Journal of Graph Theory
Título revista abreviado:J. Graph Theory
ISSN:03649024
CODEN:JGTHD
Registro:https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_03649024_v44_n3_p178_Bondy

Referencias:

  • Balakrishnan, R., Paulraja, P., Self-clique graphs and diameters of iterated clique graphs (1986) Utilitas Mathematica, 29, pp. 263-268
  • Balconi, G., Caratterizzazione matriciale dei grafi autoduali (1979) Istit Lombarde Accad Sci Lett Rend A, 113, pp. 360-365
  • Chia, G.L., On self-clique graphs with given clique sizes (2000) Discrete Math, 212, pp. 185-189
  • Cornuéjols, G., (2000) Combinatorial Optimization: Packings and Coverings, , http://integer.gsia.cmu.edu/webpub/notes.pdf, July
  • Escalante, F., Über iterierte Clique-Graphen (1973) Abhandlungender Mathematischen Seminar der Universität Hamburg, 39, pp. 59-68
  • Escalante, F., Toft, B., On clique-critical graphs (1974) J Combin Theory Ser B, 17, pp. 170-182
  • Garey, M.R., Graham, R.L., Johnson, D.S., Knuth, D.E., Complexity results for bandwidth minimization (1978) SIAM J Appl Math, 34, pp. 477-495
  • Hamelink, R.C., A partial characterization of clique graphs (1968) J Combin Theory, 5, pp. 192-197
  • Klinz, B., Rudolf, R., Woeginger, G.J., Permuting matrices to avoid forbidden submatrices (1995) Discr Appl Math, 60, pp. 223-248
  • Luks, E.M., Hypergraph isomorphism and structural equivalence of boolean functions (1999) Proceedings of the ACM Symposium of Theory of Computing, pp. 652-658. , Atlanta, Ge
  • Papadimitriou, C.H., The NP-completeness of the bandwidth minimization problem (1976) Computing, 16, pp. 263-270
  • Prisner, E., Hereditary clique-Helly graphs (1993) J Combin Math Combin Comput, 14, pp. 216-220
  • Roberts, F.S., Spencer, J.H., A characterization of clique graphs (1971) J Combin Theory Ser B, 10, pp. 102-108
  • Saxe, J.B., Dynamic-programming algorithms for recognizing small-band- -width graphs in polynomial time (1980) SIAM J Alg Disc Meth, 1, pp. 363-369
  • Szwarcfiter, J., Recognizing clique-Helly graphs (1997) Ars Combin, 45, pp. 29-32

Citas:

---------- APA ----------
Bondy, A., Durán, G., Lin, M.C. & Szwarcfiter, J.L. (2003) . Self-Clique Graphs and Matrix Permutations. Journal of Graph Theory, 44(3), 178-192.
http://dx.doi.org/10.1002/jgt.10496
---------- CHICAGO ----------
Bondy, A., Durán, G., Lin, M.C., Szwarcfiter, J.L. "Self-Clique Graphs and Matrix Permutations" . Journal of Graph Theory 44, no. 3 (2003) : 178-192.
http://dx.doi.org/10.1002/jgt.10496
---------- MLA ----------
Bondy, A., Durán, G., Lin, M.C., Szwarcfiter, J.L. "Self-Clique Graphs and Matrix Permutations" . Journal of Graph Theory, vol. 44, no. 3, 2003, pp. 178-192.
http://dx.doi.org/10.1002/jgt.10496
---------- VANCOUVER ----------
Bondy, A., Durán, G., Lin, M.C., Szwarcfiter, J.L. Self-Clique Graphs and Matrix Permutations. J. Graph Theory. 2003;44(3):178-192.
http://dx.doi.org/10.1002/jgt.10496